题目:
计算后缀表达式,操作数都是整数,操作符包括加、减、乘、除(简单起见,除法就使用整数除法),输入的算式用空格分隔。
例1:
输入:1 2 +
输出:3
例2:
输入:1 2 + 4 *
输出:12
分析:
后缀表达式的计算是栈(Stack)的典型使用场景。使用一个栈存储中间计算结果,顺序读入表达式:
1 若遇到的是整数(操作数),则入栈即可,无需其他动作
2 若遇到操作符(加、减、乘、除),则从栈顶获取2个操作数(代表最近要进行的计算),进行相应计算后再将结果入栈。可以将此动作理解为进行了一次"化简"。
3 最终,栈里应该恰好剩下一个整数,就是计算结果(如果不是这样,输入就是非法的表达式)
解一:仅考虑合法输入
#include <iostream>
#include<string>
#include<stack>
using namespace std;
bool isOp(string str){
return str=="+"||str=="-"||str=="*"||str=="/";
}
int main() {
stack<int> stack;
string word;
int tmp;
cout << "请输入后缀表达式(仅支持整数的加减乘除运算):" << endl;
while (cin >> word)
{
if(isOp(word)){
tmp=stack.top();
stack.pop();
if(word == "+"){
tmp+=stack.top();
} else if(word == "-"){
tmp=stack.top()-tmp;
}else if(word == "*"){
tmp*=stack.top();
}else if(word == "/"){
tmp=stack.top()/tmp;
} else{
cout << "不支持此运算!" << endl;
}
stack.pop();
stack.push(tmp);
} else{
int n=stoi(word);
stack.push(n);
}
if(cin.get()=='\n'){
break;
}
}
cout << "计算结果:" << stack.top() << endl;
return 0;
}
解二:考虑多种非法输入的情况
这时要考虑以下这些非法输入:
1 非法操作符
2 非法整数形式
3 除数为0(包括中间计算结果为0的情形)
4 非法算式
#include <iostream>
#include<string>
#include<stack>
using namespace std;
bool isOp(string& str){
return str=="+"||str=="-"||str=="*"||str=="/";
}
int main() {
stack<int> stack;
string word;
int tmp;
cout << "请输入后缀表达式(仅支持整数的加减乘除运算):" << endl;
while (cin >> word)
{
if(isOp(word)){
if(stack.size()<2){
cout << "非法后缀表达式!" << endl;//每个操作符都需要2个操作数在栈中
return 1;
}
tmp=stack.top();
stack.pop();
if(word == "+"){
tmp+=stack.top();
} else if(word == "-"){
tmp=stack.top()-tmp;//注意减法运算中谁是被减数。除法也同理
}else if(word == "*"){
tmp*=stack.top();
}else if(word == "/"){
if(tmp==0){
cout << "除数为0!" << endl;//除数为0的异常情形
return 1;
}
tmp=stack.top()/tmp;//为了简化,直接使用整数的除法
} else{
cout << "不支持此运算!" << endl;//只支持加减乘除
return 1;
}
stack.pop();
stack.push(tmp);
} else{
int n;
try {
n=stoi(word);
}catch (...){
cout << "请输入正确的整数!" << endl;//处理非法输入的整数形式
return 1;
}
stack.push(n);//将本次运算的结果入栈
}
if(cin.get()=='\n'){
break;
}
}
if(stack.size()==1){
cout << "计算结果:" << stack.top() << endl;//仅当栈中刚好剩余一个整数时,完成计算
return 0;
} else{
cout << "非法后缀表达式!" << endl;//栈中元素个数不为1,都属于异常情形
return 1;
}
}