一、题目来源
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
三、算法思路
本题是中缀表达式求值问题,主要为栈的应用。
思路如下:
- 首先,设置两个栈,一个为操作符栈,一个为数字栈。
- 然后,遍历整个序列:
- 遇到 ‘(‘ ,直接 (push)
- 遇到数字,直接 (push)
- 遇到操作符
- 如果是 ‘+’、‘-’,那么都可以算
-
(while) 栈不空 且 栈顶不是'(‘
- 操作
-
(while) 栈不空 且 栈顶不是'(‘
- 如果是 ‘*’、’/’,那么加减不能先算,只能算乘除
-
(while) 栈不空 且 栈顶是 ‘*’、’/’
- 操作
-
(while) 栈不空 且 栈顶是 ‘*’、’/’
- 最后 (push)
- 如果是 ‘+’、‘-’,那么都可以算
- 遇到 ‘)’
-
(while) 栈顶不是 ‘(‘
- 操作
- 将 ‘(‘ 弹出
-
(while) 栈顶不是 ‘(‘
- 处理 操作符栈中 剩余的操作符
- 数字栈的栈顶为最终答案
注意事项:
- 遇到数字要 (push),但是数字可能不是个位数,显然有可能是多位数(但不会是负数),所以需要处理一下。
- 可以将判断是否是数字、加减、乘除、操作这些抽象成函数,这样代码好写一些。
- 一定要注意,加减的运算级比乘除低,所以遇到加减可以算之前的乘除,而遇到乘除不能先算之前的加减,例如 (2+3*5),如果搞错了就会得出 (25),读者自行思考。
- 遍历完之后别忘了将剩余的操作符都要处理掉。
四、源代码
#include
using namespace std;
const int N = 100010;
char op[N];
int num[N];
int opt, numt;
void init()
{
opt = 0;
numt = 0;
}
bool isDigit(char c)
{
if (c >= '0' && c > s;
init();
for (int i = 0; i
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net