前言
最近开始刷题，真实地解决了大学时期“这黑窗口敲来敲去做数学题有卵用？”的困惑。有些东西之前学过，现在忘了，但是正是因为学过，所以再学一遍就变得效率很高（但是我还是不认可大学的学科教学顺序）。废话不多说，这篇博客只是一个笔记，希望之后有了更深的认识能够完善。
前缀、中缀以及后缀表达式是什么？
先聚合一下定义，以后万一要复习也好找XD
前缀表达式
波兰表示法（Polish notation，或波兰记法），是一种逻辑、算术和代数表示方法，其特点是操作符置于操作数的前面，因此也称做前缀表示法。
中缀表达式
中缀表示法（或中缀记法）是一个通用的算术或逻辑公式表示方法， 操作符是以中缀形式处于操作数的中间（例：3 + 4）。与前缀表达式（例：+ 3 4）或后缀表达式（例：3 4 +）相比，中缀表达式不容易被电脑解析，但仍被许多程序语言使用，因为它符合人们的普遍用法。
与前缀或后缀记法不同的是，中缀记法中括号是必需的。计算过程中必须用括号将操作符和对应的操作数括起来，用于指示运算的次序。
后缀表达式
逆波兰表示法（Reverse Polish notation，RPN，或逆波兰记法），是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式方式，在逆波兰记法中，所有操作符置于操作数的后面，因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。
对中缀表达式进行转换
这应该是基础中的基础了，理解并记忆思路，再跟着栗子走两步，最后敲一遍代码，基本就掌握了。
中缀表达式转前缀表达式
思路
- 初始化两个栈：运算符栈
S1; 操作数栈S2 - 从右至左扫描中缀表达式
- 遇到
操作数时，将其压入S2 - 遇到
运算符时，比较其与S1栈顶运算符的优先级- 如果<span style="font-weight:bold">
S1为空</span>，或栈顶运算符为右括号")"，或其优先级比栈顶运算符的优先级较高或相等，则直接将此运算符入栈 - 否则，将
S1栈顶的运算符弹出并压入到S2中，再次进行与S1栈顶运算符的优先级比较
- 如果<span style="font-weight:bold">
- 遇到
括号时- 如果是
右括号 ")"，则直接压入S1 - 如果是
左括号 "("，则依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号 ")"为止，此时将这一对括号丢弃
- 如果是
- 重复步骤 2 至 5，直到表达式的最左边
- 将
S1剩余的运算符依次弹出并压入S2 - 依次弹出
S2中的元素并输出，结果即为中缀表达式对应的前缀表达式
栗子
(1 + (3 * 4) / 6 ) - 5
| 扫描到的元素 | S2 (栈底 -> 栈顶) | S1 (栈底 -> 栈顶) | 说明 |
|---|---|---|---|
| 5 | 5 | 空 |
操作数，直接入栈 S2
|
| - | 5 | - |
运算符，S1 为空，直接入栈 |
| ) | 5 | - ) |
右括号，直接入栈 S1
|
| 6 | 5 6 | - ) |
操作数，直接入栈 S2
|
| / | 5 6 | - ) / |
运算符，且 S1 栈顶为 右括号，直接入栈 |
| ) | 5 6 | - ) / ) |
右括号，直接入栈 S1
|
| 4 | 5 6 4 | - ) / ) |
操作数，直接入栈 S2
|
| * | 5 6 4 | - ) / ) * |
运算符，且 S1 栈顶为 右括号，直接入栈 |
| 3 | 5 6 4 3 | - ) / ) * |
操作数，直接入栈 S2
|
| ( | 5 6 4 3 * | - ) / |
左括号，S1 栈弹出运算符压入 S2 直至遇到右括号，一对括号丢弃 |
| + | 5 6 4 3 * / | - ) + |
运算符，但优先级低于 S1 栈顶运算符，S1 弹出运算符压入 S2，直至栈顶优先级低于运算符，再入栈 |
| 1 | 5 6 4 3 * / 1 | - ) + |
操作数，直接入栈 S2
|
| ( | 5 6 4 3 * / 1 + | - |
左括号，S1 栈弹出运算符压入 S2 直至遇到右括号，一对括号丢弃 |
| 到达最左端 | 5 6 4 3 * / 1 + - | 空 | 将 S1 剩余的运算符依次弹出并压入 S2
|
依次弹出 S2 中的元素并输出结果： -+1/*3465
代码
中缀表达式转后缀表达式
思路
- 初始化两个栈：运算符栈
S1; 操作数栈S2 - 从左至右扫描中缀表达式
- 遇到
操作数时，将其压入S2 - 遇到
运算符时，比较其与S1栈顶运算符的优先级- 如果<span style="font-weight:bold">
S1为空</span>，或栈顶运算符为左括号 "("，或其优先级比栈顶运算符的优先级较高，则直接将此运算符入栈 - 否则，将
S1栈顶的运算符弹出并压入到S2中，再次进行与S1栈顶运算符的优先级比较
- 如果<span style="font-weight:bold">
- 遇到括号时
- 如果是
左括号 "("，则直接压入S1 - 如果是
右括号 ")"，则依次弹出S1栈顶的运算符，并压入S2，直到遇到左括号 "("为止，此时将这一对括号丢弃
- 如果是
- 重复步骤 2 至 5，直到表达式的最右边
- 将
S1剩余的运算符依次弹出并压入S2 - 拼接
S2中的元素并输出，结果即为中缀表达式对应的后缀表达式
栗子
(1 + (3 * 4) / 6 ) - 5
| 扫描到的元素 | S2 (栈底 -> 栈顶) | S1 (栈底 -> 栈顶) | 说明 |
|---|---|---|---|
| ( | 空 | ( | 左括号，直接入栈 S1
|
| 1 | 1 | ( | 操作数，直接入栈 S2
|
| + | 1 | ( + | 运算符，且 S1 栈顶为 左括号，直接入栈 |
| ( | 1 | ( + ( | 左括号，直接入栈 S1
|
| 3 | 1 3 | ( + ( | 操作数，直接入栈 S2
|
| * | 1 3 | ( + ( * | 运算符，且 S1 栈顶为 左括号，直接入栈 |
| 4 | 1 3 4 | ( + ( * | 操作数，直接入栈 S2
|
| ) | 1 3 4 * | ( + | 右括号，S1 栈弹出运算符压入 S2 直至遇到左括号，一对括号丢弃 |
| / | 1 3 4 * | ( + / | 运算符，且优先级高于 S1 栈顶的运算符，直接入栈 |
| 6 | 1 3 4 * 6 | ( + / | 操作数，直接入栈 S2
|
| ) | 1 3 4 * 6 / + | 空 | 右括号，S1 栈弹出运算符压入 S2 直至遇到左括号，一对括号丢弃 |
| - | 1 3 4 * 6 / + | - | 运算符，S1 为空，直接入栈 |
| 5 | 1 3 4 * 6 / + 5 | - | 操作数，直接入栈 S2
|
| 到达最右端 | 1 3 4 * 6 / + 5 - | 空 | 将 S1 剩余的运算符依次弹出并压入 S2
|
拼接 S2 中的元素并输出结果：134*6/+5-
代码
考题扩展
leetcode 150. 逆波兰表达式求值
根据逆波兰表示法，求表达式的值。
有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：
整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
对比上面的操作，这题考的是一个逆向思维。
思路
- 初始化一个栈
stack和一个包含+-*/操作的操作策略对象operation - 从左至右扫描逆波兰表达式
- 遇到操作数时，压入栈
stack - 遇到运算符时，依次取出栈顶的两个元素b、a（为了照顾(减)除法操作，先出栈的为被(减)除数 b ，后出栈的为(减)除数 a ），调用
operation策略对象的相应方法，并将运算结果入栈stack
- 遇到操作数时，压入栈
- 重复步骤 2，直到表达式的最右边
- 弹出栈顶元素即是运算结果
代码
波兰表达式求值
这个就举一反三就完事了。
思路
- 初始化一个栈
stack和一个包含+-*/操作的操作策略对象operation - 从右至左扫描波兰表达式
- 遇到
操作数时，压入栈stack - 遇到
运算符时，依次取出栈顶的两个元素a、b（为了照顾(减)除法操作，先出栈的为被(减)除数 a ，后出栈的为(减)除数 b ），调用operation策略对象的相应方法，并将运算结果入栈stack
- 遇到
- 重复步骤 2，直到表达式的最左边
- 弹出栈顶元素即是运算结果
代码
模拟 eval('(1 + (3 * 4) / 6 ) - 5')
思路
经过上面的熟悉和理解，这个就很简单了，只要将中缀表达式转换成后缀表达式或者前缀表达式其中的一种，再进行求值即可，代码就是把上面的组装一下，这里就不列出了。
后记
工作一段时间，算法和数据结构渐渐生疏了，在刷题的时候，又把大学的学习的知识慢慢找回来，虽然要花一段时间，但是一旦将时间投入进去，会慢慢地感兴趣，进入良性循环。
贴个GitHub，刚刚起步进行“圣地巡礼”：https://github.com/LazyDuke/leetcode-js。
