纯数组模拟

看算法基础课习题课时没有看到这道题，自己做了一下，由于对树和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;
}