用程序实现求解表达式的值,例如输入1+2*3-16/2,则输出为-1。 用栈和队列 C++
时间: 2024-10-16 12:03:08 浏览: 4
在C++中,使用栈和队列来计算这种类型的表达式通常涉及到先序遍历(Preorder Traversal)和后缀表示(Postfix Notation),也称为逆波兰表示法(Reverse Polish Notation, RPN)。这是因为栈可以帮助我们处理运算符的优先级。
首先,将原始的算术表达式转换成后缀表示(RPN)步骤:
1. 分离操作数和运算符:遇到数字就压入栈;遇到运算符则弹出栈顶的两个操作数进行运算,结果再压回栈。
2. 当遇到左括号时,压入栈;右括号出现时,直到遇到左括号为止的所有元素都会构成一个新的子表达式,此时依次计算并压回结果。
然后,从后缀表达式开始计算:
1. 初始化两个栈,一个用于存储操作数,另一个用于临时存储运算符。
2. 遍历后缀表达式,如果是数字,直接压入操作数栈;如果是运算符,从操作数栈弹出相应数量的操作数,进行计算,并把结果压回操作数栈。
3. 最终操作数栈只剩下一个元素,即为最终的计算结果。
以下是简单的C++代码示例:
```cpp
#include <stack>
#include <string>
int evalPostfix(const std::string &tokens) {
std::stack<int> values;
for (char token : tokens) {
if (isdigit(token)) { // 操作数
values.push(token - '0');
} else { // 运算符
int top = values.top();
values.pop();
int second = values.top();
values.pop();
switch (token) {
case '+': values.push(second + top); break;
case '-': values.push(second - top); break;
case '*': values.push(second * top); break;
case '/': values.push(second / top); break;
}
}
}
return values.top(); // 返回最终结果
}
// 使用示例
std::string expression = "1 2 * 3 - 16 /";
int result = evalPostfix(expression);
cout << "Result: " << result << endl; // 输出:-1
阅读全文