stack计算表达式的值

9.52 使用stack对象处理带圆括号的表达式。遇到左圆括号时，将其标记下来。当你在一个左括号之后遇到右圆括号时，弹出stack对象中这两边括号之间的元素，直到遇到左括号，将左括号也一起弹出栈。 接着在stack对象中压入一个值，用以表明这个用一对圆括号括起来的表达式已经被替换。

程序如下：

#include<iostream>
#include<stack>
#include<string>
using namespace std;

int main()
{
    stack<char> sexp;        //处理表达式的stack对象
    string exp;                //存储表达式的string对象

    //读入表达式
    cout<<"Enter a expression:"<<endl;
    cin>>exp;

    //处理表达式
    string::iterator iter=exp.begin();    //初始迭代器初始位置
    while(iter!=exp.end())
    {
        if(*iter!=')')  //读到的字符不是右圆括号
            sexp.push(*iter);   //标记字符
        else{
            //读到的是右圆括号，弹出元素直到栈顶为左圆括号或栈为空
            while(sexp.top()!='('&&!sexp.empty())
                sexp.pop();
            if(sexp.empty())        //栈为空
            {
                cout<<"parentheses are not matched"<<endl;
                return -1;
            }
            else
            {            //栈顶为左圆括号
                sexp.pop();            //弹出左圆括号
                sexp.push('@');        //表明圆括号的表达式已经被替换
            }
        }
        ++iter;
    }
    if(iter==exp.end())
        cout<<"matched"<<endl;
    return 0;
}

运行结果如下：