中缀表达式

3:中缀表达式的值

总时间限制: 

200ms

内存限制: 

1024kB

描述

人们熟悉的四则运算表达式称为中缀表达式，例如(23+34*45/(5+6+7))。在程序设计语言中，可以利用堆栈的方法把中缀表达式转换成保值的后缀表达式（又称逆波兰表示法），并最终变为计算机可以直接执行的指令，得到表达式的值。 给定一个中缀表达式，编写程序，利用堆栈的方法，计算表达式的值。

输入

第一行为测试数据的组数N 接下来的N行，每行是一个中缀表达式。表达式中只含数字、四则运算符和圆括号，操作数都是正整数，数和运算符、括号之间没有空格。中缀表达式的字符串长度不超过600。

输出

对每一组测试数据输出一行，为表达式的值

样例输入

3
3+5*8
(3+5)*8
(23+34*45/(5+6+7))

样例输出

43
64
108

提示

注意：运算过程均为整数运算（除法运算'/'即按照C++定义的int除以int的结果，测试数据不会出现除数为0的情况），输出结果也为整数（可能为负）。 中间计算结果可能为负。

 

#include<iostream>
#include<cstring>
using namespace std;
char exp[650];
char op[650];
int num[650];
int eptr, optr, nptr;
void process(char op) {
    int num2 = num[nptr --];
    int num1 = num[nptr];
    int res;
    switch(op) {
        case '+':res = num1 + num2; break;
        case '-':res = num1 - num2; break;
        case '*':res = num1 * num2; break;
        case '/':res = num1 / num2; break;
        default:res = 0;
    }
    num[nptr] = res;
}
int main() {
    int N; cin >> N;
    while (N --) {
        scanf("%s", exp);
        eptr =  optr = 0;
        nptr = -1;
        op[optr] = '(';
        int length = strlen(exp);
        exp[length] = ')';
        exp[length + 1] = '\0';
        while (exp[eptr] != '\0') {
            if (exp[eptr] >= '0' && exp[eptr] <= '9') {
                int cnum = atoi(exp + eptr);
                num[++ nptr] = cnum;
                while (eptr <= length && exp[eptr] >= '0' && exp[eptr] <= '9') eptr ++;
            }
            else {
                switch (exp[eptr]) {
                    case '(': {
                        op[++ optr] = '(';
                        break;
                    }
                    case ')': {
                        while (op[optr] != '(') {
                            process(op[optr]);
                            optr --;
                        }
                        optr --;
                        break;
                    }
                    case '-':;
                    case '+': {
                        if (op[optr] != '(') {
                            process(op[optr]);
                            optr --;
                            eptr --;//为了循环，将所有运算级别比'+'小的都算了。注意左边的'+''—'一定大于右边的
                        }
                        else
                            op[++ optr] = exp[eptr];
                        break;
                    }
                    case '/':;
                    case '*': {
                        if (op[optr] == '*' || op[optr] == '/') {
                            process(op[optr]);
                            optr --;
                            eptr --;
                        }
                        else
                            op[++ optr] = exp[eptr];
                        break;
                    }
                    default:break;
                }
                eptr ++;
            }
        }
        cout << num[0] << endl;
    }
}