栈实现无括号表达式求值
时间: 2023-05-15 19:07:50 浏览: 69
可以使用栈来实现无括号表达式求值。具体实现方法如下:
1. 创建两个栈,一个用于存储操作数,另一个用于存储操作符。
2. 从左到右扫描表达式,如果遇到操作数,则将其压入操作数栈中。
3. 如果遇到操作符,则将其压入操作符栈中。
4. 如果遇到右括号,则从操作符栈中弹出一个操作符和两个操作数,进行运算,并将结果压入操作数栈中。
5. 最终,操作数栈中只剩下一个元素,即为表达式的值。
下面是实现代码:
```
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int evaluate(string expression) {
stack<int> operands;
stack<char> operators;
for (int i = 0; i < expression.length(); i++) {
char c = expression[i];
if (isdigit(c)) {
int operand = 0;
while (i < expression.length() && isdigit(expression[i])) {
operand = operand * 10 + (expression[i] - '0');
i++;
}
i--;
operands.push(operand);
} else if (c == '+' || c == '-' || c == '*' || c == '/') {
while (!operators.empty() && operators.top() != '(' && ((c == '*' || c == '/') || (operators.top() == '+' || operators.top() == '-'))) {
int operand2 = operands.top();
operands.pop();
int operand1 = operands.top();
operands.pop();
char op = operators.top();
operators.pop();
int result;
switch (op) {
case '+':
result = operand1 + operand2;
break;
case '-':
result = operand1 - operand2;
break;
case '*':
result = operand1 * operand2;
break;
case '/':
result = operand1 / operand2;
break;
}
operands.push(result);
}
operators.push(c);
} else if (c == '(') {
operators.push(c);
} else if (c == ')') {
while (operators.top() != '(') {
int operand2 = operands.top();
operands.pop();
int operand1 = operands.top();
operands.pop();
char op = operators.top();
operators.pop();
int result;
switch (op) {
case '+':
result = operand1 + operand2;
break;
case '-':
result = operand1 - operand2;
break;
case '*':
result = operand1 * operand2;
break;
case '/':
result = operand1 / operand2;
break;
}
operands.push(result);
}
operators.pop();
}
}
while (!operators.empty()) {
int operand2 = operands.top();
operands.pop();
int operand1 = operands.top();
operands.pop();
char op = operators.top();
operators.pop();
int result;
switch (op) {
case '+':
result = operand1 + operand2;
break;
case '-':
result = operand1 - operand2;
break;
case '*':
result = operand1 * operand2;
break;
case '/':
result = operand1 / operand2;
break;
}
operands.push(result);
}
return operands.top();
}
int main() {
string expression = "3+4*5-6/2";
int result = evaluate(expression);
cout << expression << " = " << result << endl;
return 0;
}
```
这段代码实现了一个简单的无括号表达式求值程序,可以处理加、减、乘、除四种运算符。