中缀算术表达式求值
使用两个栈，操作符栈OPTR (operator)， 使用两个栈，操作符栈OPTR (operator)， 操作数栈OPND(operand)， 操作数栈OPND(operand)， 对中缀表达式求值的一般规则： 对中缀表达式求值的一般规则： (1) 建立并初始化OPTR栈和OPND栈， 建立并初始化OPTR栈和 栈和OPND栈 然后在OPTR栈中压入一个 栈中压入一个“ 然后在OPTR栈中压入一个“#” (2) 从头扫描中缀表达式，取一字符送入 从头扫描中缀表达式， ch (3) 当ch != “#” 时, 执行以下工作, 否则 执行以下工作, 结束算法， 此时在OPND 栈 结束算法 ， 此时在 OPND栈 的栈顶得 到运算结果。 到运算结果。
表达式求值
一个表达式由操作数 亦称运算对象) 一个表达式由操作数(亦称运算对象)、操 操作数( 亦称运算符) 分界符(亦称界限符) 作符 (亦称运算符) 和分界符(亦称界限符) 组成。 组成。 算术表达式有三种表示： 算术表达式有三种表示： 中缀(infix)表示 中缀 表示
<操作数> <操作符> <操作数>，如 A+B； 操作数> 操作符> 操作数> ；
① 若ch是操作数，进OPND栈，从中缀表达式 ch是操作数， OPND栈 取下一字符送入ch； 取下一字符送入ch； ch是操作符，比较栈外icp(ch)的优先级和 ② 若ch是操作符，比较栈外icp(ch)的优先级和 栈内isp(OPTR)的优先级 的优先级： 栈内isp(OPTR)的优先级： isp(OPTR)， ch进OPTR栈 若icp(ch) > isp(OPTR)，则ch进OPTR栈， 从中缀表达式取下一字符送入ch； 从中缀表达式取下一字符送入ch； isp(OPTR)，则从OPND栈 若icp(ch) < isp(OPTR)，则从OPND栈退出 a2 和 a1 ， 从 OPTR 栈 退 出 θ, 形 成 运 算 指 令 (a1)θ(a2)，结果进OPND栈； (a1)θ(a2 结果进OPND栈 “)”， 若icp(ch) == isp(OPTR) 且ch == “)”，则从 OPTR栈 退出栈顶的“ (” ， 对消括号， OPTR 栈 退出栈顶的 “ (”， 对消括号 ， 然后从 中缀表达式取下一字符送入ch； 中缀表达式取下一字符送入ch；
优先级 操作符 1 单目单目-、！ 2 *、/、% 3 +、4 <、<=、>、>= <=、 5 ==、 ==、!= 6 && 7 ||
一般表达式的操作符有4种类型: 一般表达式的操作符有4种类型: 1 算术操作符 如双目操作符（+、-、 如双目操作符（ *、/ 和%）以及单目操作符（-）; 以及单目操作符（ 2 关系操作符 包括<、<=、==、!=、 包括< <=、==、!=、 >=、 >=、>。这些操作符主要用于比较; 这些操作符主要用于比较; 3 逻辑操作符 如与(&&)、或(||)、非 如与(&&)、 (||)、 (!); 4 括号‘(’和‘)’ 它们的作用是改变 括号‘(’和 运算顺序; 运算顺序;
应用后缀表示计算表达式的值
从左向右顺序地扫描表达式， 从左向右顺序地扫描表达式 ， 并用一个 暂存扫描到的操作数 计算结果; 操作数或 栈暂存扫描到的操作数或计算结果; 在后缀表达式的计算顺序中已隐含了加 在后缀表达式的计算顺序中已 隐含了加 括号的优先次序， 括号的优先次序 ， 括号在后缀表达式中 不出现; 不出现; 计算例 a b c d - * + e f ^ g / rst1 rst2 rst3 rst6 rst4 rst5
栈内容 空 A AB ABC ABCD ABr1 Ar2 r3
步 输入 类 型 动 作 9 E 操作数 进栈 10 F 操作数 进栈 11 ^ 操作符 F、 E 退栈 计算 、 退栈, E^F, 结果 r4 进栈 12 G 操作数 进栈 13 / 操作符 G、 r4 退栈 计算 、 退栈, r4/E, 结果 r5 进栈 14 + 操作符 r5、 r3 退栈 计算 、 退栈, r3+r5, 结果 r6 进栈
中缀表达式转换为后缀表达式的算法
操作符栈初始化，将结束符‘ 进栈。 操作符栈初始化，将结束符‘;’进栈。然 后读入中缀表达式字符流的首字符ch； 后读入中缀表达式字符流的首字符ch； 重复执行以下步骤，直到ch 重复执行以下步骤，直到ch = ‘;’，同时 栈顶的操作符也是‘ 停止循环； 栈顶的操作符也是‘;’，停止循环； ch是 操作数直接输出 直接输出， 若 ch 是 操作数 直接输出 ， 读入下一个 字符ch。 字符ch。 ch是操作符，判断ch 的优先级 和 的优先级icp 若 ch是 操作符 ， 判断 ch的优先级 icp和 位于栈顶的操作符op的优先级 ： 的优先级isp 位于栈顶的操作符op的优先级isp：
若 icp (ch) > isp (op)，令ch进栈，读入 (op)， ch进栈 进栈， 下一个字符ch； 下一个字符ch； (op)，退栈并输出； 若 icp (ch) < isp (op)，退栈并输出； (op)，退栈但不输出， 若 icp (ch) == isp (op)，退栈但不输出， 若退出的是“ (”号读入下一个字符 ； 号读入下一个字符ch 若退出的是 “ (” 号读入下一个字符 ch； 算法结束， 算法结束，输出序列即为所需的后缀表 达式。 达式。
栈内容 r3E r3EF r3r4 r3r4G r3r5 r6
利表示转换成它 的前缀表示和后缀表示。 的前缀表示和后缀表示。 为了实现这种转换， 为了实现这种转换 ， 需要考虑各操作符 的优先级。 的优先级。
各个算术操作符的优先级
操作符 ch ; 栈内) isp (栈内 0 栈内 栈外) icp (栈外 0 栈外 ( 1 8 ^ *, /, % +, 7 5 3 6 4 2 ) 8 1
通过后缀表示计算表达式值的过程
顺序扫描表达式的每一项， 顺序扫描表达式的每一项，根据它的类 型做如下相应操作： 型做如下相应操作： 若该项是操作数 则将其压栈 操作数， 压栈； 若该项是操作数，则将其压栈； 若该项是操作符 操作符<op>，则连续从栈中 若该项是操作符 ， 退出两个操作数Y和 ， 退出两个操作数 和X，形成运算指令 X<op>Y，并将计算结果重新压栈。 压栈。 ，并将计算结果重新压栈 当表达式的所有项都扫描并处理完后， 当表达式的所有项都扫描并处理完后， 栈顶存放的就是最后的计算结果。 栈顶存放的就是最后的计算结果。
步 输入 类 型 动 作 1 置空栈 2 A 操作数 进栈 3 B 操作数 进栈 4 C 操作数 进栈 5 D 操作数 进栈 6 - 操作符 D、 C 退栈 计算 、 退栈, C- D, 结果 r1 进栈 7 * 操作符 r1、 B 退栈, 计算 、 退栈 B*r1, 结果 r2 进栈 8 + 操作符 r2、 A 退栈 计算 、 退栈, A*r2, 结果 r3 进栈
isp叫做栈内(in stack priority)优先数。 isp叫做栈内 叫做栈内(in priority)优先数 优先数。 icp叫做栈外(in coming priority)优先数。 icp叫做栈外 叫做栈外(in priority)优先数 优先数。 操作符优先数相等的情况只出现在括号 操作符优先数相等的情况只出现在 括号 配对或栈底的“ 号与输入流最后的“ 配对或栈底的“;”号与输入流最后的“;” 号配对时 号配对时。
a+b*(c-d)-e^f/g
rst1 rst2 rst3 rst6 rst4 rst5
表达式中相邻两个操作符的计算次序为： 表达式中相邻两个操作符的计算次序为 ： 优先级高的先计算; 优先级高的先计算; 优先级相同的自左向右计算; 优先级相同的自左向右计算; 当使用括号时从最内层括号开始计算 。
C/C++中操作符的优先级 C/C++中操作符的优先级
前缀(prefix)表示 表示 前缀
<操作符 <操作数 <操作数 ，如 +AB； 操作符> 操作数 操作数 操作符 操作数> 操作数>， ；
后缀(postfix)表示 表示 后缀
<操作数 <操作数 <操作符 ，如 AB+； 操作数> 操作数 操作符 操作数 操作数> 操作符>， ；
表达式的中缀表示