后缀表达式(也称为逆波兰表示法)的计算方法相对简单,主要依赖于栈这一数据结构。以下是计算后缀表达式的步骤:
初始化一个空栈 :这个栈用于存储操作数。从左到右遍历后缀表达式的每个元素
如果当前元素是操作数(数字),则将其推入栈中。
如果当前元素是运算符(如加号`+`、减号`-`、乘号`*`、除号`/`等),则从栈中弹出两个操作数,进行相应的运算,然后将运算结果推入栈中。
重复上述步骤,直到遍历完整个后缀表达式。
栈中剩下的唯一一个元素,即为最终的运算结果。
示例
计算后缀表达式 `3 4 + 5 *`:
1. 初始化一个空栈。
2. 遍历到 `3`,推入栈中:。
3. 遍历到 `4`,推入栈中:[3, 4]。
4. 遍历到 `+`,弹出栈顶的两个操作数 `4` 和 `3`,计算 `3 + 4 = 7`,将结果 `7` 推入栈中:。
5. 遍历到 `5`,推入栈中:[7, 5]。
6. 遍历到 `*`,弹出栈顶的两个操作数 `5` 和 `7`,计算 `7 * 5 = 35`,将结果 `35` 推入栈中:。
7. 遍历结束,栈中剩下的唯一元素是 `35`,即为最终结果。
代码实现
```cpp
include include include using namespace std; int computer(int a, char op, int b) { if (op == '+') return a + b; else if (op == '-') return a - b; else if (op == '*') return a * b; else return a / b; } int main() { stack string expression = "3 4 + 5 *"; for (int i = 0; i < expression.length(); i++) { if (isdigit(expression[i])) { s.push(expression[i] - '0'); } else { int b = s.top(); s.pop(); int a = s.top(); s.pop(); s.push(computer(a, expression[i], b)); } } cout << s.top() << endl; // 输出最终结果 return 0; } ``` 总结 后缀表达式的计算过程通过栈来处理操作数和运算符,使得计算过程更加直观和简洁。只需从左到右遍历表达式,遇到操作数就入栈,遇到运算符就弹出栈顶的两个操作数进行计算,并将结果推回栈中,最终栈中剩下的唯一元素即为表达式的计算结果。