简单计算器

[codeup 1918]

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

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

输出
对每个测试用例输出1行，即该表达式的值，精确到小数点后2位。

样例输入

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

样例输出

12178.21

//测试数据
//输入：
1+ 3 * 5 / 4 * 8 / 9 * 6 * 2 / 3/7 + 3 * 8 / 2 
12 + 78 / 4 * 6 * 7/3 - 12 - 13 - 24 * 25 / 6 
12 + 781 / 19 * 6 * 7 / 13 - 24 * 25 / 63 
985211 * 985/211 
2 / 3 * 4 
2 * 3 / 49 
5 + 2 * 3 / 49 - 4 / 13 
0 

//输出：
14.90 
160.00 
135.28 
4599207.75 
2.67 
0.12 
4.81

思路

先将中缀表达式转成后缀表达式
1.1 需要有一个存放操作符的栈和一个存放后缀表达式的队列
1.2 操作数可能不止一位，需要对一位一位进行判断是否需要合并再加入后缀表达式
1.3 操作符需要搞清楚加减乘除的优先级，可以用map来映射其中关系；同时，操作符的优先级相比，何时弹出，何时压栈，非常关键（以2 / 3 * 4为例）
1.4 如中缀表达式扫描完后，需要将剩余的操作符栈中元素依次弹出入队列
计算后缀表达式
2.1. 操作数压入栈
2.2 操作符则弹出两个操作数（后弹出为第一操作数，先弹出为第二操作数）
2.3 最后栈中存在的数即为答案

#include <cstdio>
#include <iostream>
#include <string>
#include <stack>
#include <queue>
#include <map>

using namespace std;

struct node {

    double num;     //操作数
    char op;        //操作符
    bool flag;      //操作符为false,操作数为true
};

string str;
stack<node> s;      //在change()存放操作符,在Cal()中存放操作数
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.top()为node型, node.op == '+'
                s.pop();
            }
            temp.op = str[i] ;      //将当前操作符
            s.push(temp);           // 入栈
            i++;
        }
    }//for

    while(!s.empty() ) {            //若遍历完栈中还有操作符,全部弹出
        q.push(s.top());
        s.pop();
    }
}

double Cal() {          //计算后缀表达式

    double x1,x2;
    node temp,cur;

    while(!q.empty()) {

        cur = q.front();    //cur 记录队首
        q.pop();            //出队列
        if( cur.flag == true)   s.push(cur);    //若为操作数,则入栈
        else {      //若为操作符,则弹出2个操作数

            x2 = s.top().num;   //先弹第2个数
            s.pop();
            x1 = s.top().num;   //再弹第1个数,顺序不能乱
            s.pop();

            temp.flag = true;       //临时记录一个操作数
            if(cur.op == '+') temp.num = x1 + x2;
            else if(cur.op == '-') temp.num = x1 - x2;
            else if(cur.op == '*' ) temp.num = x1 * x2;
            else if(cur.op == '/') temp.num = x1 / x2;

            s.push(temp);

        }
    }

    return s.top().num;     //最后剩下的就是结果

}

int main() {

    op['+'] = op['-'] = 1;
    op['*'] = op['/'] = 2;

    while(getline(cin,str) , str !="0") {       //getline是获取一整行的字符串

        string::iterator it ;
        for(it = str.end(); it != str.begin() ; it--) {
            if(*it == ' ')          //注意这是指针与int型的比较,不是" "
                str.erase(it);      //将字符串的空格全部清除
        }

        while(!s.empty()) s.pop();  //初始化栈,避免栈不为空,留了东西
        Change();

        printf("%.2lf\n" , Cal());


    }

    return 0;
}

感悟

需要提前考虑到因为除法而产生的浮点数，在需要的地方设置double
这一句话没有用i++形式出现，而是在需要的时候对i进行操作，妙！

for(int i=0; i<str.length(); )

需要巧妙使用map映射，在此乘除和加减的优先级不同就可用map来实现
在其中大量涉及到栈和队列的应用，必要时需要在草稿纸手动实现压栈出栈、出队入队的操作
不要遗漏细节，题目中还需要对输入时空格进行处理
拓展：添加对不合法对象的处理；如果有括号时的处理（检查左括号 '(' 和右括号 ')' )