求一个可能包含加、减、乘、除、乘方运算的中缀表达式的值。
在计算机中，我们常用栈来解决这一问题。首先将中缀表达式转换到后缀表达式，然后对后缀表达式求值。
加、减、乘、除、乘方分别用+，-，*, /, ^来表示。表达式可以有圆括号()。
时间限制：1000
内存限制：65536
输入
第一行为测试数据的组数N。 接下来的N行，每行是一个中缀表达式。 每个表达式中，圆括号、运算符和运算数相互之间都用空格分隔，运算数是整数。一般运算数可正可负（负数的符号和数字之间无空格），指数一定为自然数(0和正整数)。不必考虑除0的情况。每个运算数均可由int放下。不必考虑溢出。中缀表达式的字符串长度不超过600。乘方的优先级比乘除都高，结合性是向左结合，如2 ^ 3 ^ 4表示( 2 ^ 3 ) ^ 4 = 4096。除法的商向下取整。
输出
对每一组测试数据输出一行，为表达式的值
样例输入
2
31 * ( 5 - ( -3 + 25 ) ) + 70 ^ 2
2 * 5 + 6 * ( 7 - 8 ) + 6
样例输出
4373
10
#include <iostream>
#include <stack>
#include <string>
#include <cmath>
using namespace std;
// 定义运算符优先级函数
int youxiancixu(char op) {
if (op == '+' || op == '-')
return 1;
if (op == '*' || op == '/')
return 2;
if (op == '^')
return 3;
return 0;
}
// 定义运算函数
int yunsuan(int a, int b, char op) {
switch (op) {
case '+':
return a + b;
case '-':
return a - b;
case '*':
return a * b;
case '/':
return a / b;
case '^':
return pow(a, b);
}
return 0;
}
// 定义表达式求值函数
int evaluateExpression(string x) {
stack<int> operandStack; // 操作数栈
stack<char> operatorStack; // 运算符栈
for (char& c : x) {
if (c == ' ')
continue;
if (isdigit(c)) { // 如果是数字则入栈到操作数栈
operandStack.push(c - '0');
} else if (c == '(') { // 如果是左括号则入栈到运算符栈
operatorStack.push(c);
} else if (c == ')') { // 如果是右括号，则将栈内运算符进行计算，直到遇到左括号
while (!operatorStack.empty() && operatorStack.top() != '(') {
int b = operandStack.top();
operandStack.pop();
int a = operandStack.top();
operandStack.pop();
char op = operatorStack.top();
operatorStack.pop();
int result = yunsuan(a, b, op);
operandStack.push(result);
}
if (!operatorStack.empty() && operatorStack.top() == '(') {
operatorStack.pop(); // 弹出左括号
}
} else { // 如果是运算符
// 将栈内优先级高于或等于当前运算符的运算符进行计算，直到遇到优先级更低的运算符或左括号
while (!operatorStack.empty() && youxiancixu(c) <= youxiancixu(operatorStack.top())) {
int b = operandStack.top();
operandStack.pop();
int a = operandStack.top();
operandStack.pop();
char op = operatorStack.top();
operatorStack.pop();
int result = yunsuan(a, b, op);
operandStack.push(result);
}
operatorStack.push(c); // 当前运算符入栈
}
}
// 清空栈内剩余的运算符进行计算
while (!operatorStack.empty()) {
int b = operandStack.top();
operandStack.pop();
int a = operandStack.top();
operandStack.pop();
char op = operatorStack.top();
operatorStack.pop();
int result = yunsuan(a, b, op);
operandStack.push(result);
}
return operandStack.top(); // 返回最终计算结果
}
int main() {
int n;
if (cin >> n) { // 输入要执行的循环次数
cin.get(); // 读取掉回车符
for (int i = 1; i <= n; i++) {
string x;
getline(cin, x); // 读取表达式
int result = evaluateExpression(x); // 求值
cout << result << endl; // 输出结果
}
}
return 0;
}
【以下回答由 GPT 生成】
def is_number(char):
return char.isdigit()
def precedence(operator):
if operator == '^':
return 3
elif operator == '*' or operator == '/':
return 2
elif operator == '+' or operator == '-':
return 1
else:
return 0
def infix_to_postfix(infix_expr):
stack = []
postfix = []
operators = ['+', '-', '*', '/', '^']
for char in infix_expr.split():
if is_number(char):
postfix.append(char)
elif char == '(':
stack.append(char)
elif char == ')':
while stack and stack[-1] != '(':
postfix.append(stack.pop())
stack.pop()
elif char in operators:
while stack and precedence(stack[-1]) >= precedence(char):
postfix.append(stack.pop())
stack.append(char)
while stack:
postfix.append(stack.pop())
return ' '.join(postfix)
def evaluate_postfix(postfix_expr):
stack = []
operators = ['+', '-', '*', '/', '^']
for char in postfix_expr.split():
if is_number(char):
stack.append(int(char))
elif char in operators:
num2 = stack.pop()
num1 = stack.pop()
if char == '+':
stack.append(num1 + num2)
elif char == '-':
stack.append(num1 - num2)
elif char == '*':
stack.append(num1 * num2)
elif char == '/':
stack.append(num1 // num2)
elif char == '^':
stack.append(num1 ** num2)
return stack.pop()
while True:
try:
expr = input()
postfix_expr = infix_to_postfix(expr)
result = evaluate_postfix(postfix_expr)
print(result)
except EOFError:
break
这样，我们就完成了中缀表达式转换到后缀表达式求值的问题。请注意，由于输入多组测试数据，我们通过捕获EOFError异常来判断输入是否结束。
【相关推荐】