逆波兰式#

逆波兰式又称后缀表达式，英文名 Reverse Polish Notation，简称 RPN。

简单来说，我们日常中书写的算术表达式是中缀表达式，即以“左运算数+运算符+右运算数”为基础格式的表达式，例如 5+6、7*8；而逆波兰式则是以“左运算数+右运算数+运算符”为基础格式的表达式，例如 56+、78*。

很显然，这种书写方式对于人来说还是有点太超前了，可读性太差，所以大多数场合下根本不会有人这么写。但是对于计算机来说，常规的中缀表达式中各运算符的优先级有区别，不能按顺序直接进行计算，需要按照“有括号先算括号，先乘除，后加减”的运算规则来计算，对时间和空间的开销都很大；而后缀表达式则只需要将表达式一个一个都压入栈内，遇到运算符时直接将栈顶两个元素出栈，然后执行计算，将计算结果再入栈即可。从算法的实现上来说，后缀表达式要比中缀表达式更方便，效率也更高。

例如，如果要计算 12-(3+6*7) 这个表达式，我们可以将其转化成后缀表达式：12 3 6 7 * + -，并按照以下步骤进行计算：

先定义一个空栈 S：
```
S: 
↑
Top
```
开始逐个扫描后缀表达式，扫描到数字时将其入栈：
```
S: 12 3 6 7
          ↑
          Top
```
扫描到运算符后将栈顶两个元素出栈，用第二个出栈的元素做左运算数，第一个操作的元素做右运算数，进行计算，再将计算结果压回栈内：
```
S: 13 3 42
        ↑
        Top
```
```
S: 12 45
      ↑
      Top
```
```
S: -33
   ↑
   Top
```
扫描完表达式后将栈顶元素出栈，就是最后的得数（-33）

如何将常规运算式转化为逆波兰式#

在了解了什么是逆波兰式以后，我们需要考虑如何将常规运算式转化为逆波兰式。

我们可以建立一个数组 rpn 用来存储转化后的逆波兰式，再建立一个栈 ope 来存储运算符：

NOTE
这里为了方便我们直接用字符型变量来存储。

char rpn[MAXSIZE];

struct Stack {
	char elements[MAXSIZE];
	int top = -1;
} *ope;

然后依次遍历运算式。

NOTE
ope 的功能是按照运算优先级存储运算符，将优先级最高的运算符放到栈头，用来辅助构建逆波兰式。

在遍历运算式的过程中，如果遍历到数字我们要将其添加到 rpn 的末尾。如果遍历到运算符，我们需要判断它与之前遍历到的运算符哪个优先级更高。

根据数学运算法则：先乘除、后加减，有括号先算括号，大括号 > 中括号 > 小括号，我们可以构建一个这样的函数去判断运算优先级：

NOTE
向逆波兰式转化时，反括号的作用是匹配前面一个最近的可以匹配的正括号，它不需要做优先级判断，直接返回 0 即可。

int priority(char o) {
    switch(o) {
        case '+':
        case '-': return 1; break;
        case '*':
        case '/': return 2; break;
        case '(': return 3; break;
        case '[': return 4; break;
        case '{': return 5; break;
        default: return 0;
    }
}

然后开始遍历运算式，进行以下操作：

如果遍历到第一个运算符，由于其前面没有运算，所以无法判断其与前一个的运算符谁的优先级高，因此直接将其压入 ope 中，即如果 ope 为空，就将其压入 ope：
```
if (isEmpty(ope) == true) {
    Push(ope, exp[i]); // exp[i] 为操作符
    continue;
}
```

如果当前运算符是一个正括号，则直接将其压入 ope 中：

if (exp[i] == '(' || exp[i] == '[' || exp[i] == '{') { // exp[i] 为操作符
    Push(ope, exp[i]);
    continue;
}

如果当前运算符是一个反括号，则对 ope 执行出栈操作，并将出栈元素添加到 rpn 末尾，直到将对应的正括号出栈为止：

if (exp[i] == ')' || exp[i] == ']' || exp[i] == '}') { // exp[i] 为操作符
    while (ope->elements[ope->top] != (exp[i] == ')' ? '(' : exp[i] - 2)) { // ASCII 编码中，'(' 与 ')' 的差值为 1，而 '[' 与 ']'、'{' 与 '}' 的差值均为 2
        char e = Pop(ope);
        Append(rpn, e);
    }
    Pop(ope); // 将正括号出栈
    continue;
}

如果前一个运算符（即 ope 栈顶的运算符）的优先级小于当前运算符的优先级，说明应该优先计算当前运算符，就将当前运算符压入 ope 中：
```
if (priority(ope->elements[ope->top]) < priority(exp[i])) {
    Push(ope, exp[i]);
    continue;
}
```

如果前一个运算符（即 ope 栈顶的运算符）的优先级不小于当前运算符且前一个运算符不是正括号，说明应该优先计算前一个运算符，就将 ope 栈顶元素出栈，将其添加到 rpn 末尾，重复这个过程，直到

NOTE
以下三个条件为或的关系

ope 栈顶的运算符优先级比当前运算符小；
ope 栈为空；
ope 栈顶的运算符为正括号（( [ {）；

然后将当前运算符压入 ope 中：

if (priority(ope->elements[ope->top]) >= priority(exp[i])) { // 由于前面判断过是否为正括号，所以这里无需再次判断
    do {
        if (priority(ope->elements[ope->top]) < priority(exp[i])) break;
        if (ope->elements[ope->top] == '(' || ope->elements[ope->top] == '[' || ope->elements[ope->top] == '{') break;
        char e = Pop(ope);
        Append(rpn, e);
    } while {isEmpty(ope) == false}
    Push(ope, exp[i]);
    continue;
}

遍历结束以后，再检查 ope 是否为空，如果不为空，将剩余的栈内元素全部出栈并添加到 rpn 末尾：

while (isEmpty(ope) == false) {
    char e = Pop(ope);
    Append(rpn, e);
}

综上，可以得到将中缀表达式转化到后缀表达式的函数：

void transform2RPN(char *exp, int n) { // exp 是中缀表达式串，n 是其长度
    for (int i = 0; i < n; i++) {
        // 栈为空时
        if (isEmpty(ope) == true) {
            Push(ope, exp[i]);
            continue;
        }
        
        // 操作符为正括号时
        if (exp[i] == '(' || exp[i] == '[' || exp[i] == '{') {
            Push(ope, exp[i]);
            continue;
        }
        
        // 操作符为反括号时
        if (exp[i] == ')' || exp[i] == ']' || exp[i] == '}') {
            while (ope->elements[ope->top] != (exp[i] == ')' ? '(' : exp[i] - 2)) { // ASCII 编码中，'(' 与 ')' 的差值为 1，而 '[' 与 ']'、'{' 与 '}' 的差值均为 2
                char e = Pop(ope);
                Append(rpn, e);
            }
            Pop(ope); // 将正括号出栈
            continue;
        }
        
        if (priority(ope->elements[ope->top]) < priority(exp[i])) {
            Push(ope, exp[i]);
            continue;
        }
        
        if (priority(ope->elements[ope->top]) >= priority(exp[i])) { // 由于前面判断过是否为正括号，所以这里无需再次判断
            do {
                if (priority(ope->elements[ope->top]) < priority(exp[i])) break;
                if (ope->elements[ope->top] == '(' || ope->elements[ope->top] == '[' || ope->elements[ope-top] == '{') break;
                char e = Pop(ope);
                Append(rpn, e);
            } while {isEmpty(ope) == false}
            Push(ope, exp[i]);
            continue;
        }
    }
    while (isEmpty(ope) == false) {
        char e = Pop(ope);
        Append(rpn, e);
    }
}

计算逆波兰式#

将中缀表达式转化成后缀表达式后，我们就可以直接计算表达式的值了。

首先我们依然定义一个栈 res 用来存储计算结果。然后遍历 rpn，如果遍历值是数字，则将其压入 res 中；如果遍历值为操作符，则从栈顶出栈两个元素，出栈的第一个元素为 right，第二个元素为 left，进行计算：

int calc(int left, int right, char operate) {
    int res;
    switch(operate) {
        case '+': res = left + right; break;
        case '-': res = left - right; break;
        case '*': res = left * right; break;
        case '/': res = left / right; break;
    }
    return res;
}

计算完成后，将结果再压入栈中，继续遍历 rpn。遍历结束后，将栈顶元素出栈，即为最后结果。

int rpnCalc(char *rpn, int n) {
    Stack *res = new Stack();
    for (int i = 0; i < n; i++) {
        if (rpn[i] >= '0' && rpn[i] <= '9') {
            Push(res, rpn[i] - '0');
        } else {
            int right = Pop(res);
            int left = Pop(res);
            Push(res, calc(left, right, rpn[i]));
        }
    }
    return Pop(res);
}

TIP
这个算法只适合小于 10 的数参与的运算，如果有大于 10 的数，可以参考简单的逆波兰式求表达式值算法。