postfix evaluation的递归解法# JobHunting - 待字闺中
b*n
1 楼
Postfix evaluation 的经典解法是把数字放到堆栈里，遇到算符就把最上面的两个数
字拿出来做计算，再把结果放进堆栈，以此类推，直到结束。
还有一个从右往左扫描的递归解法:
// 假设postfix数字只有一位
double eval_postfix(const string& postfix, size_t& idx) {
char c = postfix[idx];
if (c == '+' || c == '-' || c == '*' || c == '/') {
double right = eval_postfix(postfix, ++idx);
double left = eval_postfix(postfix, ++idx);
return calc(left, c, right);
}
else
return c - '0';
}
既然堆栈的解法是从左往右扫描，有没有从左往右的递归解法？ 大家讨论讨论。
字拿出来做计算，再把结果放进堆栈，以此类推，直到结束。
还有一个从右往左扫描的递归解法:
// 假设postfix数字只有一位
double eval_postfix(const string& postfix, size_t& idx) {
char c = postfix[idx];
if (c == '+' || c == '-' || c == '*' || c == '/') {
double right = eval_postfix(postfix, ++idx);
double left = eval_postfix(postfix, ++idx);
return calc(left, c, right);
}
else
return c - '0';
}
既然堆栈的解法是从左往右扫描，有没有从左往右的递归解法？ 大家讨论讨论。