荒原之梦

中缀表达式转换成后缀表达式

从左到右遍历中缀表达式并按照如下规则生成后缀表达式：

1. 若遇到操作数（数字）则直接输出，即数字不进栈；
2. 若第一次遇到操作符（”+”, “-“, “*”, “/”）则直接将其进栈，遇到左括号 “(” 也将其进栈；
3. 之后再遇到（第 2 次及第 2 次之后遇到）操作符，则先和栈顶的操作符比较优先级。如果目前遇到的操作符（该操作符还没有进栈）的优先级不高于栈顶的操作符的优先级, 则栈内操作符依次出栈并输出直到遇到优先级低于当前遇到的操作符的操作符，或者栈为空，才可以将当前遇到的操作符进栈（从在栈中的位置来看就是低优先级的操作符不能在高优先级的操作符的上面）。
   “不高于”就是小于或等于，相同的操作符优先级相等，”*” 与 “/” 的优先级比 “+” 与 “-” 的优先级高。
4. 如果遇到右括号 “)” 则栈内元素依次出栈并输出直到遇到左括号 “(“, 但左括号只出栈而不输出，同时，右括号并不进栈。需要注意的是，只有在遇到右括号 “)” 时才把左括号 “(” 出栈，遇到其他操作符时，左括号 “(” 并不出栈；
5. 如果读到了中缀表达式末尾，则将栈内的所有元素依次出栈并输出。

示例

将中缀表达式

a+b*c+(d*e+f)*g

转换成后缀表达式。

过程如下（从左向右依次遍历并读取中缀表达式中的每个字符）：

输出结果：[NULL]
栈内情况：
栈顶
[NULL]
栈底

输出结果：a
栈内情况：
栈顶
+
栈底

输出结果：ab
栈内情况：
栈顶
+
栈底

输出结果：ab
栈内情况：
栈顶
*
+
栈底

输出结果：abc
栈内情况：
栈顶
*
+
栈底

输出结果：abc*+
栈内情况：
栈顶
[NULL]
栈底

输出结果：abc*+
栈内情况：
栈顶
+
栈底

输出结果：abc*+
栈内情况：
栈顶
(
+
栈底

输出结果：abc*+d
栈内情况：
栈顶
(
+
栈底

输出结果：abc*+d
栈内情况：
栈顶
*
(
+
栈底

输出结果：abc*+de
栈内情况：
栈顶
*
(
+
栈底

输出结果：abc+de
栈内情况：
栈顶
+
(
+
栈底

输出结果：abc+def
栈内情况：
栈顶
+
(
+
栈底

输出结果：abc+def+
栈内情况：
栈顶
+
栈底

输出结果：abc+def+
栈内情况：
栈顶
*
+
栈底

输出结果：abc+def+g
栈内情况：
栈顶
*
+
栈底

输出结果：abc+def+g*+
栈内情况：
栈顶
[NULL]
栈底

至此，我们就得到了原来中缀表达式的后缀表达式：

abc*+de*f+g*+

后缀表达式的计算

在已知后缀表达式的情况下，从左向右依次扫描该后缀表达式，遇到操作数就进栈，遇到操作符就把靠近栈顶的两个操作数出栈并进行该操作符代表的运算，计算得到的数字进栈。重复上述过程，直到后缀表达式被遍历完毕。

例如，已知 a = 6, b = 4, c = 2, d = 3, e = 2, 后缀表达式为：

abc-/de*+

则计算过程如下：

4 – 2 = 2;
6 / 2 = 3;
3 * 2 = 6;
3 + 6 = 9.

正确答案：9

前缀表达式的计算

前缀表达式的计算和后缀表达式的计算类似，只不过在计算时，若使用的是前缀表达式，则需要从右向左扫描整个式子，遇到操作数就进栈，遇到操作符就把靠近栈顶的两个操作数出栈并进行该操作符代表的运算，计算得到的数字进栈。重复上述过程，直到前缀表达式被遍历完毕。

中缀表达式转换成前缀或后缀表达式的手工计算方法

前面介绍的中缀表达式转后缀表达式的方法是适合于计算机执行的，其实，在中缀表达式不是太复杂的情况下，我们也可以使用如下方法手工得到中缀表达式的后缀表达式或前缀表达式。

例如，已知中缀表达式为：

a+b*c+(d*e+f)*g

首先，按照“先加减后乘除，从左向右依次计算”的运算优先级给原式加上括号：

((a+(b*c))+(((d*e)+f)*g))

之后，将运算符移动到它们各自括号的后面：

((a(bc)*)+(((de)*f)+g)*)+

再之后，删除所有括号即得到了后缀表达式：

abc*+de*f+g*+

若把操作符移动到它们各自括号的前面：

+(+(a*(bc))+(*(*(de)f)g))

再之后，删除所有括号即得到了前缀表达式：

++a*bc*+*defg

小贴士 1：
手工计算时，为了防止加完括号之后括号太多导致操作符移动出错，可以加一层括号就移动一个操作符到该括号的后面（或前面）；

小贴士 2：
将操作符移动括号外面时只能刚好出本层括号，而不能进入其它括号，否则，若去掉括号后有多个操作符刚好紧邻就会导致这些操作符之间的顺序发生错误从而导致后缀或前缀表达式的生成出错。

EOF

性质

A 与 B 为互斥（互不相容）事件 \Leftrightarrow A \cap B = \varnothing \Leftrightarrow A 与 B 不能同时发生。

A 与 B 为对立（互逆）事件 \Leftrightarrow A \cap B = \varnothing 且 A \cup B = \Omega \Leftrightarrow A 与 B 在一次试验中必然发生且只能发生一个.

若 P(A)=0 或 P(A)=1, 则 A 与任何事件都相互独立。

若 A 与 B 相互独立，则 P(AB)=P(A)P(B).

若 A 与 B 互斥（或互逆）且均为非零概率事件，则 A 与 B 不相互独立。

若 A 与 B 相互独立且均为非零概率事件，则 A 与 B 不互斥。

图解

A 与 B 互斥（互不相容）关系如图 1 所示：

A 与 B 对立（互逆）关系如图 2 所示：

A 与 B 相互独立关系如图 3 所示：

A 与 B 互逆，互斥与独立之间的推导关系如图 4 所示：

EOF