波兰式：将四则运算的表达式解析成一棵二叉树，后续遍历之，得到的字符串序列就是逆波兰式，也叫后缀表达式。
一开始考虑时，首先想到建立两个栈，一个栈是数字栈，一个栈是操作符栈，但是实现了一下发现不可行，重新分析发现理论上也是错误的。
考虑到后缀表达式的性质，可以很容易的确定根节点和右子树根节点(如果有的话）。四则运算表达式的二叉树的每个非叶子结点一定有两个孩子。
于是考虑使用递归，即：
1.找到根节点；
2.如果根节点数字，则返回其值；
3.如果根节点是算符op，则
计算右子树值；
计算左子树值；
返回：左子树值op右子树值
但是在上述3中，左子树的根节点位置是难以确定的，解决办法就是在递归过程中，不断"摘掉"每个访问过的点。这大概也就是为什么题目中的方法默认采用非const引用参数的原因吧。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 |
class
Solution { //实现字符串op的四则运算算符效果 int
operation(int
n1, int
n2, const
string& op) { switch
((op.c_str())[0]) { case
‘+‘: return
n1 + n2; case
‘-‘: return
n1 - n2; case
‘*‘: return
n1 * n2; case
‘/‘: return
n1 / n2; } }public: //非常精巧的递归，基本思想是利用后续遍历计算树的性质 int
evalRPN(vector<string>& tokens) { //每一次递归视作是从根节点开始计算一个树形算式，由于tokens中是后序序列，因此根节点位于最末端 string str = tokens.back(); //读取根节点值 //摘下根节点，这是由于递归时，只能预测有字数根节点的位置，无法预测左子树根节点位置， //因此必须不断摘掉树的节点，直到该字数计算完毕为止 vec.pop_back(); //如果根节点是算符，则先计算左子树值，再计算右子树值，最后用根节点算符对两个数运算，返回 //如果根节点是数字，则说明到达叶子节点，直接看做常量表达式，返回 if
(str == "+"
|| str=="-"
|| str=="*"
|| str=="/") { int
r_num = evalRPN(tokens); int
l_num = evalRPN(tokens); return
operation(l_num, r_num, str); } else
return atoi(str.c_str()); }}; |
LeetCode: Evaluate Reverse Polish Notation,布布扣,bubuko.com
LeetCode: Evaluate Reverse Polish Notation
原文：http://www.cnblogs.com/zanghu/p/3619001.html