在 C++ 程序中计算逆波兰表示法
c++server side programmingprogramming更新于 2024/11/9 8:41:00
假设我们有逆波兰表示法，并且必须计算其值。逆波兰表示法也称为后缀表达式。在这里，我们必须使用堆栈数据结构来解决后缀表达式。
从后缀表达式中，当找到一些操作数时，将它们推入堆栈。当找到某个运算符时，从堆栈中弹出两个项，然后按正确的顺序执行操作。之后，结果也被推入堆栈以备将来使用。完成整个表达式后，最终结果也存储在堆栈顶部。因此，如果表达式为"53+62/*35*+"，则答案为 39
让我们看看步骤 −
- 对于后缀表达式中的每个字符 ch，执行
- 如果 ch 是运算符 ☉ ，则
- a := 从堆栈中弹出第一个元素，
- b := 从堆栈中弹出第二个元素
- res := b ☉ a
- 将 res 推入堆栈
- 否则，如果 ch 是操作数，则
- 将 ch 添加到堆栈中
- 如果 ch 是运算符 ☉ ，则
- 返回栈顶元素
示例(C++)
让我们看下面的实现，以便更好地理解 −
#include<iostream>
#include<cmath>
#include<stack>
#include<climits>
using namespace std;
float scanNum(char ch){
int value;
value = ch;
return float(value-'0');//从字符返回浮点数
}
int isOperator(char ch){
if(ch == '+'|| ch == '-'|| ch == '*'|| ch == '/' || ch == '^')
return 1;//字符是运算符
return -1;//不是运算符
}
int isOperand(char ch){
if(ch >= '0' && ch <= '9')
return 1;//字符是操作数
return -1;//不是操作数
}
float operation(int a, int b, char op){
//执行操作
if(op == '+')
return b+a;
else if(op == '-')
return b-a;
else if(op == '*')
return b*a;
else if(op == '/')
return b/a;
else if(op == '^')
return pow(b,a); //找到 b^a
else
return INT_MIN; //返回负无穷大
}
float postfixEval(string postfix){
int a, b;
stack<float> stk;
string::iterator it;
for(it=postfix.begin(); it!=postfix.end(); it++){
//读取元素并执行后缀评估
if(isOperator(*it) != -1){
a = stk.top();
stk.pop();
b = stk.top();
stk.pop();
stk.push(operation(a, b, *it));
}
else if(isOperand(*it) > 0){
stk.push(scanNum(*it));
}
}
return stk.top();
}
main(){
string post = "53+62/*35*+";
cout << "结果为:"<<postfixEval(post);
}
输入
"53+62/*35*+"
输出
结果为:39
