简单计算器
[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来实现
- 在其中大量涉及到栈和队列的应用，必要时需要在草稿纸手动实现压栈出栈、出队入队的操作
- 不要遗漏细节，题目中还需要对输入时空格进行处理
- 拓展：添加对不合法对象的处理；如果有括号时的处理（检查左括号 '(' 和右括号 ')' )
