Codeup 简单计算器（栈的应用）

链接：Codeup 简单计算器

题目描述

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

输入

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

输出

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

样例输入

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

样例输出

12178.21

①因为要将表达式保存，所有构建结构体表示操作数/操作符，用队列存储表达式

struct node
{
    double num;    //输入为整数，但计算之后可能会是小数，所以用double类型char op;       //操作符bool is_num;   //true代表操作数，false代表操作符
};

②处理读入的中缀表达式

queue<node> read(string line)
{
    queue<node> a;node t;int i;while ((i = line.find(' ')) != string::npos)   //删除空格，便于处理。line.erase(i, 1);for (i = 0, t.num = 0; i < line.length(); i++){
    if (isdigit(line[i]))          //若该位置为数字t.num = t.num * 10 + line[i] - '0';else                   //若该位置为操作符{
    t.is_num = true;a.push(t);         //将操作数放入t.num = 0;         //记得置零t.op = line[i];t.is_num = false;a.push(t);         //再将操作符放入}if (i == line.length() - 1)   //到达末尾，将最后的操作数放入{
    t.is_num = true;a.push(t);}}return a;
}

ps.
str.find( ch )： 在字符串str中找到字符ch并返回其下标，若没找到则返回string::npos

str.erase( first , second )： 删除字符串str中迭代器[ first , second) 的所有字符
str.erase( pos , n )： 删除字符串str中下标pos开始的n个字符

③中缀表达式转为后缀表达式
1）建立一个栈存放操作符，建立一个队列存放后缀表达式;
2）从左到右遍历中缀表达式，遇到操作数就放入后缀表达式中；
3）若碰到操作符op——保证栈顶操作符优先级严格大于下面的
　a. op优先级＞栈顶操作符优先级，op入栈
　b. op优先级 ≤ 栈顶操作符优先级，令操作符出栈并放入后缀表达式中，直至 op优先级＞栈顶操作符优先级 或 栈为空，再令op入栈
4）遍历完后，将栈中剩余操作符出栈并放入后缀表达式中。

ps.
若有括号，那么碰见左括号 ( 直接令其入栈，碰见右括号 ) 就不断出栈直至遇到