后缀表达式 | Some Notes

基本的

定义

后缀表达式，也叫逆波兰表达式，指的就是将运算符置于运算数之后。前缀表达式亦然。平时使用的是中缀表达式。
其实，也就是将表达式表示成表达式树。前、中、后缀表达式分别是这个树的前、中、后序遍历。
由于后缀表达式运算的顺序就是从左往右，所以它不需要括号。

转换

例如 $14 + (1 + 2) \times (7 - (6 \div 2))$ ，表示为：

mermaid-expr-tree

使用后序遍历即表示为 $1412 + 762 \div - \times +$ ，这就是它的后缀表达式。它们的结果都是 $26$ 。

实现计算

演示

后缀表达式的模拟用栈实现，仅维护数字栈。其实就是把每一个数字压进栈，遇到符号时，就将栈顶两个元素弹出进行运算，再把结果重新压进栈。例如当栈顶元素是 $s_{1}$ ，弹出 $s_{1}$ 后栈顶元素是 $s_{2}$ 。遇到符号减号，将两个元素弹出，加入 $s_{2} - s_{1}$ 。

其实就是：

s_{1} s_{2} \to s_{2} - s_{1}

例如上面表达式树的栈的演示：

+ 2114 \to / 267314 \to - 37314 \to * 4314 \to + 1214 \to 26

代码

洛谷 P1449
和上面的栈是一样的。

完整代码

#include <cstdio>
#include <stack>
#include <cstdlib>
using namespace std;

int n, m;
stack<int> stk;
char s[53];
int main()
{
    scanf("%s", &s);
    
    char ts[53];
    int cnt = 0;
    for(int i = 0; s[i] != '\0'; i++)
    {
        if(s[i] == '@') break;

        if(s[i] == '.')
        {
            int temp = atoi(ts); // 将记录的所有数字字符转化为数字
            // printf("temp:%d\n", temp);
            stk.push(temp);
            for(int i = 0; i <= cnt; i++){ts[i] = ' ';}
            cnt = 0;
        }
        else if(s[i] >= '0' && s[i] <= '9') ts[cnt++] = s[i];
        else
        {
            int temp1 = stk.top();
            stk.pop();
            int temp2 = stk.top();
            stk.pop();
            // printf("t1:%d t2:%d op:%c\n", temp2, temp1, s[i]);
            switch(s[i])
            {
                case '+':
                    stk.push(temp2 + temp1);
                    break;
                case '-':
                    stk.push(temp2 - temp1);
                    break;
                case '*':
                    stk.push(temp2 * temp1);
                    break;
                case '/':
                    stk.push(temp2 / temp1);
                    break;
            }
        }
    }

    printf("%d", stk.top());

    return 0;
}