theme: channing-cyan
AcWing 3302. 表达式求值
题目描述
给定一个表达式，其中运算符仅包含 +,-,*,/（加 减 乘 整除），可能包含括号，请你求出表达式的最终值。
注意：
- 数据保证给定的表达式合法。
- 题目保证符号
-只作为减号出现，不会作为负号出现，例如，-1+2,(2+2)*(-(1+1)+2)之类表达式均不会出现。 - 题目保证表达式中所有数字均为正整数。
- 题目保证表达式在中间计算过程以及结果中，均不超过 2^31−1。
- 题目中的整除是指向 0 取整，也就是说对于大于 0 的结果向下取整，例如 5/3=1，对于小于 0 的结果向上取整，例如 5/(1−4)=−1。
- C++和 Java 中的整除默认是向零取整；Python 中的整除
//默认向下取整，因此 Python 的eval()函数中的整除也是向下取整，在本题中不能直接使用。
输入格式
共一行，为给定表达式。
输出格式
共一行，为表达式的结果。
数据范围
表达式的长度不超过 10^5。
输入样例：
(2+2)*(1+1)
输出样例：
8
C++
#include <iostream>
#include <algorithm>
#include <stack>
#include <unordered_map>
using namespace std;
// 用于存储操作数的栈
stack<int> num;
// 用于存储操作符的栈
stack<char> op;
// 执行一次计算操作
void eval() {
// 获取并弹出栈顶的两个操作数
auto b = num.top();
num.pop();
auto a = num.top();
num.pop();
// 获取并弹出栈顶的操作符
auto c = op.top();
op.pop();
int x;
// 根据操作符进行相应的计算
if (c == '+') x = a + b;
else if (c == '-') x = a - b;
else if (c == '*') x = a * b;
else x = a / b;
// 将计算结果压回操作数栈
num.push(x);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// 定义操作符优先级的映射
unordered_map<char, int> pr{{'+', 1},
{'-', 1},
{'*', 2},
{'/', 2}};
string str;
// 读取输入的表达式
cin >> str;
// 遍历输入的表达式
for (int i = 0; i < str.size(); i++) {
auto c = str[i];
// 如果当前字符是数字
if (isdigit(c)) {
int x = 0, j = i;
// 提取完整的数字
while (j < str.size() && isdigit(str[j]))
x = x * 10 + str[j++] - '0';
// 更新索引i
i = j - 1;
// 将数字压入操作数栈
num.push(x);
}
// 如果当前字符是左括号
else if (c == '(') op.push(c);
// 如果当前字符是右括号
else if (c == ')') {
// 处理所有括号内的操作符
while (op.top() != '(') eval();
// 弹出左括号
op.pop();
}
// 如果当前字符是操作符
else {
// 处理优先级高于或等于当前操作符的操作符
while (!op.empty() && op.top() != '(' && pr[op.top()] >= pr[c]) eval();
// 将当前操作符压入操作符栈
op.push(c);
}
}
// 处理栈中剩余的操作符
while (!op.empty()) eval();
// 输出最终结果
cout << num.top() << endl;
return 0;
}
Go
package main
import (
"container/list"
"fmt"
)
// 用于存储操作数的栈
var num *list.List
// 用于存储操作符的栈
var op *list.List
// 执行一次计算操作
func eval() {
// 获取并弹出栈顶的两个操作数
b := num.Remove(num.Back()).(int)
a := num.Remove(num.Back()).(int)
// 获取并弹出栈顶的操作符
c := op.Remove(op.Back()).(rune)
var x int
// 根据操作符进行相应的计算
switch c {
case '+':
x = a + b
case '-':
x = a - b
case '*':
x = a * b
case '/':
x = a / b
}
// 将计算结果压回操作数栈
num.PushBack(x)
}
func main() {
// 定义操作符优先级的映射
pr := map[rune]int{'+': 1,
'-': 1,
'*': 2,
'/': 2}
num = list.New()
op = list.New()
var str string
fmt.Scan(&str)
// 遍历输入的表达式
for i := 0; i < len(str); i++ {
c := rune(str[i])
// 如果当前字符是数字
if '0' <= c && c <= '9' {
x := 0
j := i
// 提取完整的数字
for j < len(str) && '0' <= rune(str[j]) && rune(str[j]) <= '9' {
digit := int(str[j] - '0')
x = x*10 + digit
j++
}
// 更新索引i
i = j - 1
// 将数字压入操作数栈
num.PushBack(x)
} else if c == '(' { // 如果当前字符是左括号
op.PushBack(c)
} else if c == ')' { // 如果当前字符是右括号
// 处理所有括号内的操作符
for op.Back().Value.(rune) != '(' {
eval()
}
// 弹出左括号
op.Remove(op.Back())
} else { // 如果当前字符是操作符
// 处理优先级高于或等于当前操作符的操作符
for op.Len() > 0 && op.Back().Value.(rune) != '(' && pr[op.Back().Value.(rune)] >= pr[c] {
eval()
}
// 将当前操作符压入操作符栈
op.PushBack(c)
}
}
// 处理栈中剩余的操作符
for op.Len() > 0 {
eval()
}
// 输出最终结果
fmt.Println(num.Back().Value.(int))
}