堆疊問題

template <class T, int N=512> struct Stack
{
    T   d[N];      //資料項
    int n;         //元素個數  
    Stack()        { n = 0; }
    void push (T x){ d[n++] = x; }
    T pop()        { return d[--n]; } 
    T& operator*() { return d[n-1]; }
    T& operator[] (int i) { return d[i]; }
};

double calculate (Stack<char>& s)
{
    Stack<double> v;
    char c; double d;

    for (int i=0; i<s.n; i++) 
    {
        c = s[i];
        if (Ɔ'<=c && c<=Ə') { 
            v.push (c-Ɔ'); 
            continue; 
        }
        d = v.pop();
        switch (c) {
           case'+': *v += d; break;
           case'-': *v -= d; break;
           case'*': *v *= d; break;
           case'/': *v /= d; break;
        }        
    }
    return *v;
}

void main()
{
    Stack<char> num, op;                   //num 放後序式, op 放運算符
    char c, pri[128], *p = "8*(1+9)-8/2";  //pri=運算元優先權
    int i=128;

    while (i--) pri[i] = 3;
    pri['*']= pri['/'] = 2; 
    pri['+']= pri['-'] = 1; 
    pri[')']= 0; 
    pri['(']= 5;
   
    for (;c=*p; c^')'? op.push(c): op.pop(), p++)     
        while (pri[c] <= pri[*op] && '('!=*op) 
            num.push (op.pop());        
    while (op.n > 0) num.push (op.pop());
    
    for (i=0; i<num.n; i++) cout<<num[i];   //印出 postfix
    cout <<endl <<calculate (num);          //印出運算結果
}