问题 C: 某计算器的超电磁炮
题目描述
输入由非负整数、+、-、*、/、(、)组成的计算表达式，计算该表达式的值。
输入
每个输入文件中一组数据。
输入只有一行，不超过200个字符，其中不存在空格。数据保证表达式一定合法，且所有的整数都不小于0、不大于1024。中间结果保证不超过15位有效数位精度。
输出
输出一行，即表达式的值，结果精度保留小数点后2位。
样例输入
3+(12/(2*2+1))样例输出
5.40提示
晴神书（算法笔记）上第七章的基础上加上对左括号和右括号的处理就行。如果 str[i]是左括号，那么入操
作符栈；如果 str[i]是右括号，那么不断把操作符栈中的元素弹出到后缀表达式队列中，直到
碰到左括号。注意左括号跟右括号都是不需要进入后缀表达式中的。具体看代码。
#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 if(str[i] == '(') { // 如果是左括号
temp.op = str[i];
s.push(temp); // 直接入操作符栈
i++;
} else if(str[i] == ')') { // 如果是右括号
while(!s.empty() && s.top().op != '(') { // 只要还没有到达左括号
q.push(s.top()); // 将操作符栈顶不断弹出到后缀表达式的队列中
s.pop();
}
s.pop(); // 弹出左括号，不入队
i++;
} 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(); //cur记录队首元素
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[')'] = 0;
op['+'] = op['-'] = 1; //设定操作符的优先级
op['*'] = op['/'] = 2;
getline(cin, str);
Change(); //将中缀表达式转换为后缀表达式
printf("%.2f\n", Cal()); //计算后缀表达式
return 0;
}