算法10——c++实现中缀表达式计算

题目描述：
  读入一个只包含+,-,x,/的非负整数计算表达式，计算该表达式的值

输入格式：
  测试输入包含若干测试用例，每个测试用例占一行，每行不超过200个字符，整数和运算符之间用一个空格分隔。没有非法表达式。当一行中只有0时输入结束，相应的结果不用输出

输出格式：
  对每个测试用例输出一行，即该表达式的值，精确到小数点后两位

样例输入：

30/90-26+97-5-6-13/88*6+51/29+79*87+57*92
0

样例输出：

12178.21

思路：

• 中缀表达式转后缀表达式
• 对后缀表达式进行计算

中缀表达式转后缀表达式：

• 设立一个操作符栈，用以临时存放操作符；设立一个数组或者队列，用以存放后缀表达式
• 从左至右扫描中缀表达式，如果碰到操作数(注意：操作数可能不止一位)，就把操作数加入后缀表达式中
• 如果碰到操作符op，就将op与栈顶操作符优先级进行比较。如果op的优先级高于栈顶操作符的优先级，那么op就压入操作符栈；反之，操作符栈不断弹出操作符加入到后缀表达式中，直到op的优先级高于栈顶操作符的优先级，然后将栈顶操作符压入操作符栈
• 重复以上操作，直到中缀表达式扫描完毕，之后若操作符栈仍有元素，则将它们依次弹出加入后缀表达式

计算后缀表达式：

  从左到右扫描后缀表达式，如果是操作数，就压入栈；如果是操作符，就连续弹出操作数(先弹出的是第二操作数，后弹出的是第一操作数)，然后进行操作符的操作，生成新的操作数压入栈中。直到后缀表达式扫描完毕，这是栈中只会存在最后的结果

代码：

#include<iostream>
#include<cstdio>
#include<string>
#include<stack>
#include<queue>
#include<map>
using namespace std;

struct node{
    double num;//操作数
    char op;//操作符
    bool flag;//true表示操作数，false表示操作符
};

string str;
stack<node> s;//操作符栈
queue<node> q;//后缀表达式序列
map<char,int> op;

void Change(){//中缀表达式转后缀表达式
    double num;
    node temp;
    for(int i = 0 ; i < str.length();){
        if(str[i]>='0'&&str[i]<='9'){
            //如果是数字
            temp.flag = true;
            temp.num = str[i++]-'0';
            while(i<str.length()&&str[i]>='0'&&str[i]<='9'){
                //后面一位还是数字，说明这个数还没取完
                temp.num = temp.num*10+(str[i]-'0');
                i++;
            }
            q.push(temp);//加入后缀表达式序列
        }else{
            //如果是操作符
            temp.flag = false;
            //只要操作符栈的栈顶元素比该操作符优先级高
            //就把操作符栈栈顶元素弹出加入到后缀表达式
            while(!s.empty()&&op[str[i]]<=op[s.top().op]){
                q.push(s.top());
                s.pop();
            }
            temp.op = str[i];
            s.push(temp);
            i++;
        }
    }
    //如果操作符栈中还有操作符，就将它弹出加入后缀表达式
    while(!s.empty()){
        q.push(s.top());
        s.pop();
    }
}

 double Cal(){
        //计算后缀表达式
        double temp1,temp2;
        node cur,temp;
        while(!q.empty()){
            cur = q.front();//记录队首元素
            q.pop();
            if(cur.flag==true){
                //如果是操作数，直接压入栈
                s.push(cur);
            }else{
                temp2 = s.top().num;//第二个操作数
                s.pop();
                temp1 = s.top().num;//第一个操作数
                s.pop();
                temp.flag = true;//标记临时操作数
                if(cur.op == '+')
                    temp.num = temp1+temp2;
                else if(cur.op == '-')
                    temp.num = temp1 - temp2;
                else if(cur.op == '*')
                    temp.num = temp1 * temp2;
                else
                    temp.num = temp1 / temp2;
                s.push(temp);
            }
        }
        return s.top().num;
}

int main(){
    op['+'] = op['-'] = 1;
    op['*'] = op['/'] = 2;
    while(getline(cin,str),str!="0"){
        for(string::iterator it = str.end();it!=str.begin();it--){
            if(*it == ' ')
                str.erase(it);//把表达式中的空格删除
        }
        while(!s.empty())
            s.pop();//初始化栈
        Change();
        printf("%.2f\n",Cal());
    }
    return 0;
}