典型应用场合
-
逆序输出 (conversion)
输出次序与处理过程颠倒, 递归深度和输出长度不易预知
-
递归嵌套 (stack permutation + parenthesis)
具有自相似性的问题可递归描述, 但分支位置和嵌套深度不固定
-
延迟缓冲 (evaluation)
线性扫描算法模式中, 在预读足够长之后, 方能确定可处理的前缀
-
栈式计算 (RPN)
基于栈结构的特定计算模式
RPN
逆波兰表达式 (Reverse Polish Notation), 又称后缀表达式
J.Lukasiewicz (12/21/1878 - 02/13/1956)
例如: 0! + 123 + 4 * ( 5 * 6! + 7! / 8 ) / 9 => 0 ! 123 + 4 5 6 ! * 7 ! 8 / + * 9 /
在由运算符 (operator) 和操作数 (operand) 组成的表达式中不使用括号 (parenthesis-free), 即可表达带优先级的运算关系
体验
infix 到 postfix: 手工转换
例如: ( 0 ! + 1 ) ^ ( 2 * 3 ! + 4 - 5 )
假设: 事先未就运算符之间的优先级关系做过任何约定
-
用括号显式地表达式优先级
{ ( [ 0 ! ] + 1 ) ^ ( [ ( 2 * [ 3 ! ] ) + 4 ] - 5 ) } -
将运算符移到对应的右括号后
{ ( [ 0 ] ! 1 ) + ( [ ( 2 [ 3 ] ! ) * 4 ] + 5 ) - } ^ -
抹去所有括号, 即得
0 ! 1 + 2 3 ! * 4 + 5 - ^
infix 到 postfix: 转换算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
float evaluate(char *S, char *&RPN) { // RPN 转换
/* ....................................... */
while (!optr.empty()) { // 逐个处理各字符, 直至运算符栈空
if (isDigit(*S)) { // 若当前字符为操作数, 则直接将其
readNumber(S, opnd); append(RPN, opnd.top()); // 接入 RPN
} else { // 若当前字符为运算符
switch (orderBetween(optr.top(), *S)) {
/* ........................ */
case '>': // 且可立即执行, 则在执行相应计算的同时将其
char op = optr.pop(); append(RPN, op); // 接入 RPN
/* .................... */
break;
/* ........................ */
}
}
}
}
本文由
Oscaner
创作, 采用
知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外, 均为本站原创或翻译, 转载前请务必署名
