AcWing 3302. 表达式求值
原题链接
简单
作者:
不回
,
2023-05-18 17:57:25
,
所有人可见
,
阅读 119
暴力出奇迹,打表过样例,哈哈哈自行看注释吧
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int numst[N],numtop,chtop;
char chst[N];
int l[N],ltop = 0,r[N],rtop = 0;
void init(){
numtop = 0;
chtop = 0;
}
bool isnum(char x){
if(x >= '0'&&x <= '9') return 1;
return 0;
}
int count(char s[],int &idx,int len){
int ans = 0;
while(isnum(s[idx]) && idx < len){
ans *= 10;
ans += s[idx ++] -'0';
}
idx --;
return ans;
}
int main(){
char s[N];
scanf("%s",s);
int len = strlen(s);
for(int i = 0;i < len;i ++){
if(isnum(s[i])) numst[++ numtop] = count(s,i,len);
else if(s[i] == '+' || s[i] == '-') chst[++ chtop] = s[i];
else if(s[i] == '(') r[++ rtop] = numtop,chst[++ chtop] = s[i],l[++ ltop] = chtop;
else if(s[i] == '*'){
if(isnum(s[i + 1])){
i ++;
numst[numtop] *= count(s,i,len);
}
else chst[++ chtop] = '*';
}
else if(s[i] == '/'){
if(isnum(s[i + 1])){
i ++;
numst[numtop] /= count(s,i,len);
}
else chst[++ chtop] = '/';
}
else if(s[i] == ')'){
for(int i = l[ltop] + 1,j = r[rtop] + 2;i <= chtop;i ++,j ++){
if(chst[i] == '+') numst[r[rtop] + 1] += numst[j];
else if(chst[i] == '-') numst[r[rtop] + 1] -= numst[j];
}
chtop = l[ltop --] - 1;
numtop = r[rtop --] + 1;
if(chst[chtop] == '*'){
numst[numtop - 1] *= numst[numtop];
chtop --;
numtop --;
}
else if(chst[chtop] == '/'){
numst[numtop - 1] /= numst[numtop];
chtop --;
numtop --;
}
}
}
int ans = numst[1],idx = 1,numidx = 2;
while(idx <= chtop){
if(chst[idx] == '+') ans += numst[numidx];
else if(chst[idx] == '-') ans -= numst[numidx];
idx ++;
numidx ++;
}
cout << ans;
return 0;
}