前中後序運算式-2

　
以下程式說明了當運算子很多時，
最好用 reverse polish 的 stack 解法，而不要做 recursive descent，
否則 60 幾行可完成的 code 會變成好幾百行...

#include <iostream>
#include <ctype.h>
using namespace std;

template <class T, int N=512>
class Stack
{
    T err (int n)
    {
        static char* s[] = {
            "Overflow","Underflow",
            "Out of range","Empty"
        };
        puts (s[n]); getch(); 
        return d[0];
    }
public:
    T d[N];                //資料項
    int n;                 //元素個數  
    Stack()               { n = 0; }
    void push (T x)       { if (n<N) d[n++] = x; else err(0);}
    T pop()               { return n? d[--n]: err(1); }
    T& operator*()        { return n>0? d[n-1]: err(3); }
    T& operator[] (int i) { return 0<=i&&i<n? d[i]: err(2); }
};
class Expression
{
    char *s, c, *p, buf[512];     

    void next () {c = *s++;}

    void put (char c1, char c2=0) {
        *p++ = c1;
        if (c2 != 0) *p++ = c2;
    }

    int expr ()
    {
        if (!or()) return 0;
        while (c=='|') {
            next(); if(c != '|') return 0;
            next(); if(!or()) return 0;
            put ('|','|');
        }return 1;
    }
    int or ()
    {
        if (!and()) return 0;
        while (c=='&') {
            next(); if(c != '&') return 0;
            next(); if(!and()) return 0;
            put ('&','&');
        }return 1;
    }
    int and ()
    {
        if (!compar()) return 0;
        char op[3] = {0,0,0};
        while (c=='<' || c=='>') {
            op[0] = c;
            next(); if(c == '=') {op[1]='='; next();}
            if(!compar()) return 0;
            put (op[0], op[1]);
        }return 1;
    }
    int compar ()
    {
        if (!term()) return 0;
        for (char op; c=='+' || c=='-';) {
            op = c; next(); if(!term()) return 0;
            put (op);
        }return 1;
    }
    int term ()
    {
        if (!fact()) return 0;
        for (char op; c=='*' || c=='/';) {
            op = c; next(); if (!fact()) return 0;
            put (op);
        }return 1;
    }
    int fact ()
    {
        if (!expo()) return 0;
        while (c=='^') {
            next(); if (!expo()) return 0;
            put ('^');
        }return 1;
    }
    int expo ()
    {
        if (c == '!') {
            next(); if(!invers()) return 0;
            put ('!');
        }
        else if (!invers()) return 0;
        return 1;
    }
    int invers ()
    {
        if (isalpha(c)) {
            put (c);  
            next(); return 1;
        }
        else if (c=='(') {
            next();  
            if (expr() && c == ')') {
                next(); return 1;
            }
        }return 0;
    }
   
    //---------------------------------
    struct Node
    {
        char c[3];
        Node *L,*R;
        Node () { c[1]=c[2]=0; L=R=0; }
        Node (char c1, char c2=0, Node* l=0, Node* r=0) {
            c[0]=c1; c[1]=c2; c[2]=0; L=l; R=r;
        }
        Node (char c1, Node* l, Node* r) {
            c[0]=c1; c[1]=0; L=l; R=r;
        }
    };

    Node* build_exptree (char* postfix)
    {
        Stack <Node*> s;
        Node *o, *L, *R;
        char c1, c2, *p = postfix;
        
        while(*p)
        {
            if(isalpha(*p) || isdigit(*p))
            {
                s.push (new Node(*p));
            }
            else
            {
                c1 = *p; c2 = 0;
                L = 0;               
                R = s.pop();
                if (c1 != '!') L = s.pop();
                if (c1=='&'||c1=='|') c2 = *++p;
                else if ((c1=='<'||c1=='>')&& p[1]=='=')
                    c2 = *++p;
                s.push (new Node (c1, c2, L, R));
            }
            p++;
        }
        return s.pop();
    }

    void preorder (Node *x)
    {
        if(x != NULL) {
            cout << x->c;
            preorder (x->L);
            preorder (x->R);
        }
    }

    void inorder (Node *x)
    {
        if(x != NULL) {
            preorder (x->L);
            cout << x->c;
            preorder (x->R);
        }
    }
    void postorder (char* exp)
    {
        p = buf; s = exp; next();
        expr(); put(0);
    }
    //-----------------------------------

public:
    void postfix (char* exp)
    {
        postorder (exp); cout << buf;
    }

    void prefix (char* exp)
    {
        postorder (exp);
        preorder (build_exptree (buf));
    }        
};


void main (/* daviddr */)
{
    char* s[] = {
        "(a-b*(c+d)^e)&&((f+g^h)-i*j+k/l)",
        "!((a^b-c/d+e/f))||(g-(h^i+j*k)/l+m)",
        "(a-b/c)*d^f<=(g+h*i)/j+k^l-m"
    };
    Expression exp;

    for (int i=0; i<3; i++) {
        puts(""); exp.postfix(s[i]);
        puts(""); exp.prefix (s[i]);
    }
}