运用Y总模板写出的模拟栈

其实使用栈的思路在题解中已经有大佬很详细的解释过了，这里放一个链接：
https://www.acwing.com/solution/content/40978/
因此对于栈的使用这里就不再赘述
这里主要是借鉴了这个大佬的思路，尝试用Y总的模拟栈模板解题

C++ 代码(注释版)

#include<iostream>
using namespace std;
const int N = 1e5 + 10;

int num[N];
char op[N];
int ntt = 0, optt = 0;

char h[100];

void init()
{
    h['+'] = 1, h['-'] = 1, h['*'] = 2, h['/'] = 2;
}//初始化优先级
void push_num(int x) 
{
    num[ntt++] = x;
}//操作数入栈
void push_op(char c) 
{
    op[optt++] = c;
}//运算符入栈
bool isdigits(char c) 
{
    if(c >= '0' && c <= '9') {
        return true;
    }
    else return false;
}//判断是否是数字
void eval()
{
//在push()的时候，是先输入num[ntt]的值，再将ntt+1
//所以此时将操作数取出计算时，就应该先将ntt-1,再进行计算 -> --ntt
//optt同理
    int nd = num[--ntt]; //第二个操作数
    int st = num[--ntt]; //第一个操作数

    char p = op[--optt]; //运算符

    int res = 0; //结果

    if(p == '+') {
        res = st + nd;
    }
    else if(p == '-') {
        res = st - nd;
    }
    else if(p == '*') {
        res = st * nd;
    }
    else if(p == '/') {
        res = st / nd;
    }
    push_num(res); //num.push()
}
int main()
{
    string str;
    cin >> str;
    init();//初始化
    for(int i = 0; i < str.size(); ++i) {
        if(isdigits(str[i])) {
            //计算数字,将string转化为int
            int j = i;
            int x = 0;
            while(j < str.size() && isdigits(str[j])) {
                x = x*10 + (str[j] - '0');
                ++j;
            }
            push_num(x); //num.push()
            i = j - 1;
        }
        else if(str[i] == '(') {
            push_op(str[i]); //op.push()
        }// '(' 无优先级，直接入栈
        else if(str[i] == ')') {
            while(op[optt-1] != '(') {
            //!注意是optt-1，不是optt，原因参考eval函数中注释
            //下同，数组[]内都是ntt-1 / optt-1
                eval();
            }
            optt--; //pop()
        }// 遇到')'直接进入计算，直到遇到'('
        else {
            while(optt && h[op[optt-1]] >= h[str[i]]) { 
                //第一个判断条件 optt -> op.empty()

                eval();
            }
            push_op(str[i]);//op.push()
        }// (+ - * /) 四则运算
    }

    while(optt) eval();
    //进行剩下的计算
    cout << num[ntt-1] << endl;
    //输出
    return 0;
}

然后因为水平有限，花了很长的时间才成功AC
主要的卡点就在于边界的判断，eval()中的–ntt, –optt 一开始写成了ntt–, optt–
然后数组中的optt - 1, ntt - 1, 写成了optt, ntt
还有一个比较低级的错误是 x = x * 10 + (str[j] - ‘0’); 写成了 x += x * 10 + (str[j] - ‘0’);
然后放一个我做题时的测试代码吧，无注释，感兴趣的小伙伴可以看看

C++代码 (测试版)

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int num[N];
char op[N];
int ntt = 0, optt = 0;
char h[100];
void init()
{
    h['+'] = 1, h['-'] = 1, h['*'] = 2, h['/'] = 2;
}
void push_num(int x) {
    num[ntt++] = x;
}
void push_op(char c) {
    op[optt++] = c;
}
bool isdigits(char c) {
    if(c >= '0' && c <= '9') {
        return true;
    }
    else return false;
}
void eval()
{
    // printf("eval:\n");
    // printf("before: ntt = %d, optt = %d\n", ntt, optt);
    int nd = num[--ntt];
    int st = num[--ntt];

    char p = op[--optt];
    // printf("after: ntt = %d, optt = %d\n", ntt, optt);
    // printf("p = %c\n", p);

    int res = 0;

    if(p == '+') {
        res = st + nd;
    }
    else if(p == '-') {
        res = st - nd;
    }
    else if(p == '*') {
        res = st * nd;
    }
    else if(p == '/') {
        res = st / nd;
    }
    // printf("%d %c %d = %d\n", st, p, nd, res);
    push_num(res);
}
int main()
{
    string str;
    cin >> str;
    init();
    for(int i = 0; i < str.size(); ++i) {
        // for(int i = 0; i < optt; ++i) {
        //     printf("op[%d] = %c\n",i, op[i]);
        // }
        // for(int i = 0; i < ntt; ++i) {
        //     printf("num[%d] = %d\n",i, num[i]);
        // }
        // printf("ntt = %d, optt = %d\n", ntt, optt);
        // if(optt >= 1) {
        //     printf("op[optt-1] = %c, str[i] = %c\n",op[optt-1], str[i]);
        //     printf("h[op[optt-1]] = %d, h[str[i]] = %d\n",h[op[optt-1]], h[str[i]]);
        // }
        // printf("\n");

        if(isdigits(str[i])) {
            int j = i;
            int x = 0;
            while(j < str.size() && isdigits(str[j])) {
                x = x*10 + (str[j] - '0');
                ++j;
            }
            push_num(x);
            i = j - 1;
        }
        else if(str[i] == '(') {
            push_op(str[i]);
        }
        else if(str[i] == ')') {
            while(op[optt-1] != '(') {
                eval();
            }
            optt--;
        }
        else {
            while(optt && h[op[optt-1]] >= h[str[i]]) {
                // printf("ohhhhhhhh!\n");
                eval();
            }
            push_op(str[i]);
        }// + - * /
    }
    while(optt) eval(); 

    // for(int i = 0; i < optt; ++i) {
    //     printf("op[%d] = %c\n",i, op[i]);
    // }
    // for(int i = 0; i < ntt; ++i) {
    //     printf("num[%d] = %d\n",i, num[i]);
    // }
    // printf("ntt = %d\n", ntt);
    cout << num[ntt-1] << endl;
    return 0;
}

第一次写题解，有写的不好的地方还请见谅~