C++實例(表達式求值(棧的應用))

表達式求值：
    設計一個程序實現輸入一個表達式如3*(3+4)，以”#”結尾，求出其值。
    分析：
    先分析一下四則運算的規(guī)則：
    1. 先乘除后加減；
    2. 從左到右計算；
    3. 先括號內后括號外；
    于是我們要把運算符的優(yōu)先級確定清楚。這里我只用這幾個運算符：+-*/()，
    可以知道+-的優(yōu)先級低于*/，而對于()，當第一次遇到’(‘時，’(‘后面的就優(yōu)先計算，直到遇到’)’為止，可以先把’(’的優(yōu)先級定為比其它幾個都高，然后遇到’)’時把里面的先算出來，再算括號外面的，具體實現在代碼中會表現得很清楚。
    考試2大提示這個程序還是用棧來實現，具體代碼如下。
    代碼：
    #include
    #include
    using namespace std;
    const int STACK_INIT_SIZE=100; //The maximize length of stack
    template class Stack //A class of stack
    {
    public:
    Stack() //Constructor function
    {
    base = new int[STACK_INIT_SIZE];
    if (!base)
    {
    cerr<<"Fail to assign memory!"<    exit(-1);
    }
    top=base;
    stacksize=STACK_INIT_SIZE;
    }
    ~Stack() //Destructor function
    {
    if (base) delete[] base;
    }
    T GetTop()
    {
    if (top==base)
    {
    cerr<<"Empty!"<    exit(-1);
    }
    return *(top-1);
    }
    void Push(T e)
    {
    if (top-base>=stacksize)
    {
    base=new int[STACK_INIT_SIZE];
    if(!base)
    {
    cerr<<"Fail to assign memory!"<    exit(-1);
    }
    top=base+STACK_INIT_SIZE;
    stacksize+=STACK_INIT_SIZE;
    }
    *top++=e;
    }
    void Pop(T& e)
    {
    if (top==base)
    {
    cerr<<"Empty!"<    exit(-1);
    }
    e=*--top;
    }
    private:
    int *base;
    int *top;
    int stacksize;
    };
    string op("+-*/()#"); //The set of operator
    bool In(char c,string op) //Judge the character whether belong to the set of operator
    {
    string::iterator iter=op.begin();
    for (;iter!=op.end();++iter)
    if (*iter==c) return true;
    return false;
    }
    char Precede(char top,char c) //Confirm the precedence of operator
    {
    int grade_top=0,grade_c=0;
    switch (top)
    {
    case '#':grade_top=0;break;
    case ')':grade_top=1;break;
    case '+':grade_top=2;break;
    case '-':grade_top=2;break;
    case '*':grade_top=3;break;
    case '/':grade_top=3;break;
    case '(':grade_top=4;break;
    }
    switch (c)
    {
    case '#':grade_c=0;break;
    case ')':grade_c=1;break;
    case '+':grade_c=2;break;
    case '-':grade_c=2;break;
    case '*':grade_c=3;break;
    case '/':grade_c=3;break;
    case '(':grade_c=4;break;
    }
    if (grade_top>=grade_c) {
    if (top=='('&&c!=')')
    return '<';
    else if (top=='('&&c==')')
    return '=';
    return '>';
    }
    else if (top=='#'&&c=='#') return '=';
    else return '<';
    }
    int Operate(int a,char theta,int b) //Calculate
    {
    if (theta=='+') return a+b;
    else if (theta=='-') return a-b;
    else if (theta=='*') return a*b;
    else if (theta=='/') return a/b;
    return 0;
    }
    int EvaluateExpression(Stack& OPTR,Stack& OPND)
    {
    int a=0,b=0,n=0;
    char x;
    char theta;
    string c;
    cin>>c;
    OPTR.Push('#');
    while (c[0]!='#'||OPTR.GetTop()!='#')
    {
    if (!In(c[0],op)){
    n=atoi(&c[0]);
    OPND.Push(n);
    cin>>c;
    }
    else
    switch (Precede(OPTR.GetTop(),c[0]))
    {
    case '<':
    OPTR.Push(c[0]);
    cin>>c;
    break;
    case '=':
    OPTR.Pop(x);
    cin>>c;
    break;
    case '>':
    OPTR.Pop(theta);
    OPND.Pop(b);
    OPND.Pop(a);
    OPND.Push(Operate(a,theta,b));
    break;
    }
    }
    return OPND.GetTop();
    }
    int main()
    {
    Stack OPTR;
    Stack OPND;
    cout<<"Please input your expression,end of '#':"<    cout<    return 0;
    }