题目描述】

小明在你的帮助下，破密了Ferrari设的密码门，正要往前走，突然又出现了一个密码门，门上有一个算式，其中只有“(”，“)”，“0-9”，“+”，“-”，“*”，“/”，“^”，求出的值就是密码。小明数学学得不好，还需你帮他的忙。(“/”用整数除法)

【输入】

共1行，为一个算式。

【输出】

共1行，就是密码。

【输入样例】

1+(3+2)*(7^2+6*9)/(2)

【输出样例】

258

#include <cmath>
#include <iostream>
using namespace std;

const int N = 255;
int n[N] = {0};
char c[N] = {0};

bool first(char ch1, char ch2)
{//判断ch1是否比ch2优先级高
    if (ch1 == '^') {//优先级最高
        return true;
    }
    if (ch2 == '^') {//优先级最高
        return false;
    }
    if (ch2 == ')') {//优先级最低
        return true;
    }
    if (ch1 == '-' || ch1 == '+') {//优先级较低
        if (ch2 == '-' || ch2 == '+') {
            return true;
        }
        return false;
    }
    if (ch1 == '*' || ch1 == '/') {//优先级较高
        return true;
    }
    return false;
}

int calc(int a, int b, char op)
{
    switch (op) {
        case '+':
            return a + b;
        case '-':
            return a - b;
        case '*':
            return a * b;
        case '/':
            return a / b;
        case '^':
            return pow(a, b);
    }
    return 0;
}

void show(int ntop, int ctop)
{
    for (int i = 0; i < ntop; i++) {
        cout << n[i] << " ";
    }
    cout << "; ";
    for (int i = 0; i < ctop; i++) {
        cout << c[i] << " ";
    }
    cout << endl;
}

int main()
{
    char ch = 0;
    int a = 0, b;
    int ntop = 0, ctop = 0;
    while (ch != '@') {//结束
        //cout<<"ntop:"<<ntop<<endl;
        ch = cin.get();
        switch (ch) {
            case '+':
            case '-':
            case '*':
            case '/':
            case '^':
                n[ntop++] = a;
                while (ctop > 0 && first(c[ctop - 1], ch)) {
                    b = n[--ntop];
                    a = n[--ntop];
                    n[ntop++] = calc(a, b, c[--ctop]);
                }
                c[ctop++] = ch;
                //show(ntop,ctop);
                a = 0;
                break;
            case '(':
                c[ctop++] = ch;
                break;
            case ')':
                n[ntop++] = a;
                //show(ntop,ctop);
                while (ctop > 0 && c[ctop - 1] != '(' && first(c[ctop - 1], ch)) {
                    b = n[--ntop];
                    a = n[--ntop];
                    n[ntop++] = calc(a, b, c[--ctop]);
                }
                //show(ntop,ctop);
                if (c[ctop - 1] == '(') {//弹出(
                    a = n[--ntop];
                    ctop--;
                }
                //show(ntop,ctop);
                break;
            default:
                if (ch >= '0' && ch <= '9') {
                    a = a * 10 + (ch - '0');
                } else {//结束
                    n[ntop++] = a;
                    while (ctop > 0) {
                        //show(ntop,ctop);
                        b = n[--ntop];
                        a = n[--ntop];
                        n[ntop++] = calc(a, b, c[--ctop]);
                    }
                    ch = '@';
                }
                break;
        }
    }
    cout << n[--ntop];
    return 0;
}