初赛一些知识

前缀，中缀，后缀（逆波兰）表达式

中缀表达式

中缀表达式是一个通用的算术或逻辑公式表示方法。其实中缀表达式跟我们平常见到的数学式子是一样的。

例如：1*（2+3）

---

前缀表达式
前缀表达式又称波兰表达式，，前缀表达式的运算符位于操作数之前

例如：- × + 3 4 5 6

前缀表达式求值
从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 op 次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果

例如：- × + 3 4 5 6

1. 从右至左扫描，将6、5、4、3压入堆栈
2. 遇到+运算符，因此弹出3和4（3为栈顶元素，4为次顶元素，注意与后缀表达式做比较），计算出3+4的值，得7，再将7入栈
3. 接下来是×运算符，因此弹出7和5，计算出7×5=35，将35入栈
4. 最后是-运算符，计算出35-6的值，即29，由此得出最终结果

中缀表达式转前缀表达式

方法:
我们设两个栈表，s1 s2.
从右到左遍历中缀表达式
如果遇到数字，将其压入s1中
如果遇到运算符时（s2）：

1. 若栈为空或栈顶的符号为’)’，直接压入s2中
2. 若栈顶的运算符的优先级小于或等于当前符号，直接压入s2中
3. 否则将s2中的栈顶运算符弹出，压入s1，再次转到(4-1)与s1中新的栈顶运算符相比较

遇到括号时

1. 如果是右括号“)”，则直接压入s1
2. 如果是左括号“(”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号为止，此时将这一对括号丢弃

重复步骤2至5，直到表达式的最左边
将s1中剩余的运算符依次弹出并压入s2
依次弹出s2中的元素并输出，结果即为中缀表达式对应的前缀表达式

---

后缀表达式
后缀表达式又称逆波兰表达式,与前缀表达式相似，只是运算符位于操作数之后

例如:3 4 + 5 × 6 -

后缀表达式求值
从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 op 次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果

与前缀同理，这里就不做例子了

中缀表达式转后缀表达式

方法:
我们设两个栈表，s1 s2.
从左到右遍历中缀表达式
如果遇到数字，将其压入s1中
如果遇到运算符时（s2）：

1. 若栈为空或栈顶的符号为’(’，直接压入s2中
2. 若栈顶的运算符的优先级小于或等于当前符号，直接压入s2中
3. 否则将s2中的栈顶运算符弹出，压入s1，再次转到(4-1)与s1中新的栈顶运算符相比较

遇到括号时

1. 如果是左括号“(”，则直接压入s1
2. 如果是右括号“)”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到左括号为止，此时将这一对括号丢弃

重复步骤2至5，直到表达式的最左边
将s1中剩余的运算符依次弹出并压入s2
依次弹出s2中的元素并输出，结果即为中缀表达式对应的后缀表达式（转换为后缀表达式时不用逆序）

更新中…