AcWing 3302. 纯数组模拟后缀表达式-表达式求值
原题链接
简单
作者:
sungchien
,
2023-01-25 19:51:48
,
所有人可见
,
阅读 126
纯数组模拟
看算法基础课习题课时没有看到这道题,自己做了一下,由于对树和stl容器之类不太熟悉,用了数组模拟,期间遇到问题时翻看题解也没有看到数组模拟的方法,于是写一个题解,分享一下菜鸟的思路
#include<iostream>
using namespace std;
const int N=100010;
char cal[N];
int num[N], num_top=-1, op[N], op_top=-1, cate[N];
//num存储数字,op存储第一次遍历到的操作符
//cate表示种类,1表示这一位存的是操作符的ascii码,0表示这一位是数字
int is_Prior(int a, int b){//a优先于b返回1,否则返回0
if(a=='*'||a=='/'){
if(b=='+'||b=='-'||b=='(') return 1;
else return 0;
}else if(a!='('&& b=='(') return 1;
else return 0;
}
int calcu(int a, int b, int op){
if(op=='*') return a*b;
if(op=='/') return a/b;
if(op=='+') return a+b;
if(op=='-') return a-b;
}
int main(){
scanf("%s", cal);
for(int i=0; cal[i]!=0; i++){
int number=0;
if(cal[i]>='0'&&cal[i]<='9'){
while(cal[i]>='0'&&cal[i]<='9') {
number=number*10 +(cal[i]-'0');
i++;
}
i--;
num[++num_top]=number; //数字直接放进数字栈
cate[num_top]=0;
}else if(cal[i]==')'){ //如果当前为右括号')'
while(op[op_top]!='(') {
num[++num_top]=op[op_top--]; //遇到右括号就将符号栈中左括号之前的操作符依次压入数字栈
cate[num_top]=1;
}
op_top--;//舍弃左括号
}
else{//如果为除右括号以外的其他符号
char c=cal[i];
if(op_top<0 || c=='(') op[++op_top] = c; //符号栈为空或者当前为左括号 直接进栈
else if( is_Prior(c, op[op_top]) ){//如果栈顶符号优先级低
op[++op_top] = c;//此符号进栈
}else{ //如果栈顶优先级不低
while(op_top>=0 && !is_Prior(c, op[op_top])) {
num[++num_top]=op[op_top--];
cate[num_top]=1;
}
op[++op_top] = c;
}
}
}
while(op_top>=0) {
num[++num_top]=op[op_top--];
cate[num_top]=1;
}
//此时op栈为空,数字和操作符以后缀表达式的顺序存储在num[]数组中
//******************上面求后缀表达式,下面根据后缀表达式计算***********************
//回收利用op数组,将他作为临时数组存储数字
for(int i=0; i<=num_top; i++){ //遍历后缀表达式(num[]数组),数字为压入临时栈(op[])中
if(cate[i]==0) { //数字位
op[++op_top]=num[i];
}
else{ //遇到操作符弹出两个数字计算结果并再次压入临时数组中
int b=op[op_top--], a=op[op_top--];
op[++op_top]=calcu(a, b, num[i]);
}
}
//此时op[]中只有一个数,num栈为空
printf("%d\n", op[op_top]); //输出最终结果
return 0;
}