任何一个表达式都是由操作数（Operand）、运算符（Operator）和界限符（Delimiter）组成的：
- 操作数可以是常数，也可以是变量或常量的标识符；
- 运算符可以分为算术运算符、关系运算符和逻辑运算符；
- 基本界限符有左右括号和表达式结束符。
习惯上，把运算符和界限符统称为算符。
为了简化问题，本节讨论的表达式假设是由 +, - ,*, / 以及正整数和圆括号组成的合法的算术表达式，显然，这种表达式可以由用户通过键盘输入，程序中得到了一个相应的字符串或字符数组，例如：exp = '1 + 2 * (4 - 3)' 。
常用的表达式的形式，有如下三种：
-
中缀表达式（Infix Expression）：在算术表达式中，运算符位于操作数中间的表达式。例如
1 + 2 * 3。对于算术四则运算，遵循以下 3 条规则：
(1) 先乘除，后加减;
(2) 从左算到右;
(3) 先括号内，后括号外中缀表达式，不仅要依赖运算符优先级，还要处理括号。
-
后缀表达式（Postfix Expression），或称为逆波兰表示法（Reverse Polish Notation, RPN）：在算术表达式中运算符在操作数的后面，例如
1 + 2 * 3的后缀表达式为1 2 3 * +。这种形式的表达式是由波兰数学家扬·卢卡西维茨于1920年引入的。后缀表达式广泛应用于利用栈进行运算的计算机中，以减少计算机内存访问。 -
前缀表达式（Prefix Expression），或称为波兰表示法（Polish Notation）：运算符置于操作数的前面。例如
1 + 2 * 3的前缀表达式为+ 1 * 2 3。这种形式的表达式是由波兰数学家扬·武卡谢维奇于1920年代引入的，用于简化命题逻辑，如应用在 LISP 编程语言（起源于 1958 年的一种编程语言）。
1. 中缀表达式转换成后缀表达式
尽管后缀表达式不够直观易读，但它不需要括号，只有操作数和运算符，并且越放在前面的运算符越优先执行，也就是考虑了运算符的优先级。具体而言，各运算符被执行的次序，与其在后缀表达式中出现的次序完全吻合。下面介绍两种转换方法。
（1） 手工转换
例 4.4.1 将中缀表达式 5 + (1 + 2) * 4 - 3 转换为后缀表达式。
【解】
-
对中缀表达式，按照计算的优先级，增添足够多的括号，用以显示地指定表达式的运算次序：
((5 + ((1 + 2) * 4)) - 3) -
按照“从里到外”的顺序，将每层括号的运算符移到与之紧邻的对应的右括号的右侧：
((5 + ((1 2) + * 4)) - 3)((5 + ((1 2) + 4) *) - 3)((5 ((1 2) + 4) *) + - 3)((5 ((1 2) + 4) *) + 3) -
-
去掉左右的括号：
5 1 2 + 4 * + 3 -，最终得到后缀表达式。
可见，后缀表达式和中缀表达式相比，操作数之间的相对次序，在转换前后保持不变；而运算符在后缀表达式中所处的位置，恰好就是其对应的操作数均已就绪且该运算可以执行的位置。以上述得到的后缀表达式为例，如果用手工方式计算：
- 计算
1 2 +，即1 + 2 = 3，于是得到5 3 4 * + 3 - - 计算
3 4 *，得到5 12 + 3 - - 计算
5 12 +，得到17 3 - - 最后得到结果：14
（2）利用栈转换
利用栈将中缀表达式转换为后缀表达式的基本流程是：对中缀表达式从左到右扫描，将遇到的操作数直接存放到后缀表达式中，将遇到的每一个运算符或者左括号都暂时保存到运算符栈，而且先执行的运算符先出栈。
例 4.4.2 中缀表达式 exp = '1 + 2 + 3' ，利用栈转换为后缀表达式。
【解】
-
将操作数
1存入后缀表达式序列postexp，即postexp = '1'； -
遇到第一个
+，尚未确定它是否最先执行，将其进栈。至此得到图 4.4.13 所示结果：
-
将操作数
2存入到postexp，即postexp = 1 2； -
遇到第二个
+，比较两个+的优先级，如果第二个+进栈，则以后它一定要先出栈，表示第二个+比第一个+先执行，显然这是错误的，按照执行顺序，应该先执行第第一个+。所以，此时应该先将栈中的第一个+出栈，并存入postexp，即得到：postexp = 1 2 +；然后将第二个+入栈（表示第一个+先执行）。此时得到图 4.4.4 所示结果：
-
将操作数
3存入到postexp，即postexp = 1 2 + 3； -
对
exp扫描完毕，将运算符栈中的第二个+出栈，并存入postexp，得到：postexp = 1 2 + 3 +，即为后缀表达式。
归纳 1： 在扫描 exp 遇到一个运算符 op 时：
-
如果栈为空，直接将其进栈；
-
如果栈不空：
-
只有当
op的优先级高于栈顶运算符的优先级时才直接将op进栈（以后op先出栈表示先执行它）； -
否则依次出栈运算符并存入
postexp（出栈的运算符都比op先执行）。直到
op的优先级高于栈顶运算符为止，即将op进栈。
-
例 4.4.3 中缀表达式 exp = '2 * (1 + 3) - 4' ，利用栈转换为后缀表达式。
【解】
-
将操作数
2存入后缀表达式序列postexp，即：postexp = '2'； -
遇到
*，将其进栈； -
遇到
(，将其进栈； -
将操作数
1存入postexp，即postexp = 2 1； -
遇到
+，将其进栈； -
将操作数
3存入postexp，即postexp = 2 1 3； -
遇到
)，如图 4.4.5 所示，出栈+，并存入postexp（postexp = 2 1 3 +）出栈(；
图 4.4.5 栈内的运算符
-
遇到
-，出栈*，并存入postexp（postexp = 2 1 3 + *），将-进栈； -
将操作数
4存入postexp（postexp = 2 1 3 + * 4）； -
此时
exp扫描完毕，出栈-，并存入postexp。得到的最后结果postexp = 2 1 3 + * 4 -。
归纳 2： 在扫描 exp 遇到一个运算符 op 时，
- 如果
op为(，表示一个子表达式的开始，直接将其进栈； - 如果
op为)，表示一个子表达式的结束，需要出栈运算符并存入postexp，直到栈顶为(，再将(出栈（但不存入postexp）； - 如果
op是其他运算符，而栈顶为(，直接将其进栈（但不存入postexp）。
综上，可以将中缀表达式 exp 转换成后缀表达式 postexp 的过程写成如下流程：
//设 Optr 是运算符栈，初始为空while(从 exp 读取字符 ch, ch!='\0'){ch 为数字: 将后续的所有数字均依次存放到 postexp 中;ch 为左括号 "(": 将此括号进栈到 Optr 中;ch 为右括号 ")": 将 Optr 中出栈时遇到的第一个左括号 "(" 以前的运算符依次出栈并存放到 postexp 中, 然后将左括号 '(' 出栈;ch 为其他运算符:if(栈空或者栈顶运算符为 '(') 直接将 ch 进栈;else if (ch 的优先级高于栈顶运算符的优先级)直接将 ch 进栈;else依次出栈并存入到 postexp 中, 直到 ch 的优先级高于栈顶运算符, 然后将 ch 进栈;
}
若 exp 扫描完毕, 则将 Optr 中的所有运算符依次出栈并存放到 postexp 中。
例 4.4.4 将表达式 (56 - 20) / (4 + 2) 转换为后缀表达式。
【解】
转换过程如下表所示：
| 操作 | postexp | Optr 栈（栈底 → 栈顶） |
|---|---|---|
ch 为 '('，将此括号进栈 | ( | |
ch 为数字，将 56 存入 postexp 中 | 56 | ( |
ch 为 ‘-’ ，直接将 ch 进栈 | 56 | ( - |
ch 为数字，将 20 存入 postexp 中 | 56 20 | ( - |
ch 为 ) ，将栈中 ( 之前的运算符 - 出栈并存入 postexp 中，然后将 ( 出栈 | 56 20 - | |
ch 为 / ，将 ch 进栈 | 56 20 - | / |
ch 为 '('，将此括号进栈 | 56 20 - | / ( |
ch 为数字，将 4 存入 postexp 中 | 56 20 - 4 | / ( |
ch 为 +，由于栈顶运算符为 ( ，则直接将 ch 进栈 | 56 20 - 4 | / ( + |
ch 为数字，将 2 存入 postexp 中 | 56 20 - 4 2 | / ( + |
ch 为 ) ，将栈中 ( 之前的运算符 + 出栈并存入 postexp 中，然后将 ( 出栈 | 56 20 - 4 2 + | / |
str 扫描完毕，则将 Optr 栈中的所有运算符依次出栈并存入 postexp 中，得到最终的后缀表达式 | 56 20 - 4 2 + / |
【算法描述】
void trans(char *exp, char postexp[]){//将中缀表达式 exp 转换成后缀表达式 postexpchar e;SqStack * optr; //定义顺序栈InitStack(optr); //初始化int i = 0; //i 作为 postexp 的下标while( *exp != '\0'){ //exp 表达式未扫描完时循环switch(*exp){case '(': //判定为左括号Push(optr, '('); //左括号入栈exp++; //继续扫描其他字符break;case ')': //判定为右括号Pop(optr, e); //出栈while(e != '('){//不为 ( 时循环postexp[i++] = e; //将 e 存放到 postexp 中Pop(optr, e); //继续出栈元素 e}exp++;break;case '+': //判定为加号或减号case '-':while(!StackEmpty(optr)){//栈不空循环GetTop(optr, e); //获取栈顶元素if(e != '('){postexp[i++] = e;Pop(optr, e);} else{ // e 是 ( 时退出循环break;}}Push(optr, *exp); //将+或-进栈exp++;break;case "*":case "/":while(!StackEmpty(optr)){GetTop(optr, e);if(e == '*' || e == '/'){postexp[i++] = e;Pop(optr, e);} else {break;}}Push(optr, *exp);exp++;break;default: //处理数字字符while(*exp >= '0' && *exp <= '9'){postexp[i++] = *exp;exp++;}postexp[i++]='#'; //用 # 标识一个数字结束或字符之间的分隔}}while(!StackEmpyt(optr)){//此时 exp 扫描完毕，栈不为空时循环Pop(optr, e);postexp[i++] = e;}postexp[i] = '\0'; //给postexp表达式添加结束标识DestroyStack(optr); //销毁栈
}
