用栈将算术表达式转换成后缀表达式的形式大家应该不陌生了,但是我在实现计算的时候却发现坑还是不少。
题目描述: 读入一个只包含 +, -, *, / 的非负整数计算表达式,计算该表达式的值。
输入描述: 测试输入包含若干测试用例,每个测试用例占一行,每行不超过200个字符,整数和运算符之间用一个空格分隔。没有非法表达式。当一行中只有0时输入结束,相应的结果不要输出。
输出描述: 对每个测试用例输出1行,即该表达式的值,精确到小数点后2位。
示例1 输入
1 + 2 4 + 2 * 5 - 7 / 11 0
输出
3.00 13.36
做这题必须注意几个问题:
- 当栈里没有运算符的时候,直接对栈顶和字符串读取到的运算符进行比较会出错,因此这里在一开始就往栈里压入了一个我们设计的符号'#'
- 当我们遍历字符串的时候,遇到数字要格外注意,因为此时一切都是字符形式了,比如说输入11就会变成两个字符1,因此我们在读取的时候要进行判断,确保所有连在一起的数字字符都读到了,而不是只读到了第一个字符。
- 当我们遍历完字符串的时候,很有可能栈里还留有没处理的运算符,因此我们需要继续处理栈里的操作符,这里在字符串后面加入了符号\$是很巧妙的,\$的优先级比'#'高,比其他符号低,因此这保证了当读到字符\$时,它一定比栈顶出现的所有字符优先级高(除了它自己和'#'),这样就可以让栈里剩下的运算符一个一个弹出来,至到处理结束,栈顶为'#',压入\$。
具体代码如下:
#include<iostream>
#include<stack>
#include<string>
#include<stdio.h>
#include<cctype>
using namespace std;
/**
* 比较操作符优先级的函数
*/
int OperPrecedence(char a){
if(a == '/' || a == '*'){
return 3;
}else if(a == '+' || a == '-' ){
return 2;
}else if(a == '$'){
return 1;
}else if(a == '#'){
return 0;
}
}
/**
* 实现运算
*/
double operNums(char oper, double num1, double num2){
if(oper == '+'){
return num1 + num2;
}else if(oper == '-'){
return num1 - num2;
}else if(oper == '*'){
return num1 * num2;
}else if(oper == '/'){
return num1 / num2;
}
}
/**
* 实现遇到数字往后移动直到数字确定
*/
int getNum(string str, int &index){
string num = "";
while(isdigit(str[index])){
num += str[index];
index ++;
}
return atoi(num.c_str());
}
int main(){
stack<char> operStack;
stack<double> numStack;
string str;
char oper;
double num1;
double num2;
double sum = 0;
int index = 0, preceResult;
operStack.push('#');
while (getline(cin, str))
{
str += '$';
if(str[0] == '0'){
break;
}
while(index < str.size()){
if(str[index] == ' '){
index++;
}
else if(isdigit(str[index])){
//数字
numStack.push(getNum(str, index));
}else
{
//操作符
//比较优先级
if(OperPrecedence(operStack.top()) < OperPrecedence(str[index])){
operStack.push(str[index]);
index++;
}else{
num2 = numStack.top();
numStack.pop();
num1 = numStack.top();
numStack.pop();
oper = operStack.top();
operStack.pop();
numStack.push(operNums(oper, num1 ,num2));
}
}
}
// std::cout << "sum="<<sum << endl;
printf("%.2f\n", numStack.top());
index = 0;
}
}