牛牛与后缀表达式

后缀表达式转中缀表达式

1、建立一个栈，从左向右扫描后缀表达式，遇到运算数则压入栈；

2、遇到运算符就把栈顶两个元素出栈，执行运算，得到的结果作为新的运算符再压入栈；

3、依次走到表达式结尾；

例如后缀表达式 "12#3#+15#*"， 转化为中缀表达式为：

1. 数值 12 入栈
2. 数值 3 入栈
3. 遇到运算符 '+' ，将 12 和 3 出栈，执行加法操作得到 15， 再把 15 入栈
4. 数值 15 入栈
5. 遇到运算符 '*' ，将 15 和 15 出栈，执行乘法操作得到 225， 再把 225 入栈。

最后栈内的元素 225 就是最后的答案。

这题直接开个栈模拟一下就行，注意要开 long long.

读数字的话，可以用类似于快读的方法来读取。

Code

    long long solve(string str) {
        int n = str.length();
        long long sta[1000010];
        int i = 0, top = 0;
        long long s = 0;
        while(1)
        {
            if(i >= n) break;
            char ch = str[i];
            if(ch == '#')//读数字
            {
                sta[++top] = s;
                s = 0;
            }
            else if(ch == '+')//加法操作
            {
                long long a = sta[top--];
                long long b = sta[top--];
                sta[++top] = a+b;
            }
            else if(ch == '-')//减法操作
            {
                long long a = sta[top--];
                long long b = sta[top--];
                sta[++top] = b-a;
            }
            else if(ch == '*')//乘法操作
            {
                long long a = sta[top--];
                long long b = sta[top--];
                sta[++top] = a * b;
            }
            else 
            {
                s = s * 10 + str[i] - '0';
            }
            i++;
        }
        return sta[top];
    }