1+ # -*- coding: utf-8 -*-
2+
3+ class Solution :
4+ # @param expression: a list of strings;
5+ # @return: an integer
6+ def evaluateExpression (self , expression ):
7+ # write your code here
8+ '''
9+ 先转换成后缀表达式，然后再计算后缀表达式的值。
10+ 后缀表达式转换步骤：
11+ 1. 定义两个堆栈，表达式栈ex和运算符栈op。
12+ 2. 从左到右扫描中缀表达式
13+ 3. 遇到操作数，直接进ex。
14+ 4. 遇到运算符，与op栈顶元素比较优先级
15+ - 4.1. 如果op为空，或者栈顶运算符为'('，入栈。
16+ - 4.2. 若优先级高于op栈顶运算符，入站。
17+ - 4.3. 弹出op栈顶元素压入ex，再次转到4.1。
18+ 5. 如果运算符是'('或'))'
19+ - 5.1. '('直接入栈
20+ - 5.2. 如果是')'，一次将op栈操作符弹出并入压ex栈，直到遇到'('，抛弃匹配括号。
21+ 6. 重复2到5
22+ 7. 将op栈内剩余元素依次弹出并压入ex栈。
23+ 关于后缀表达式的计算自己google去。
24+ '''
25+ op_rank = {'+' : 1 , '-' :1 , '*' :2 , '/' : 2 , '(' : 3 , ')' : 3 }
26+ post_expr = []
27+ op_stack = []
28+ for item in expression :
29+ if self .isOperand (item ): # #1
30+ post_expr .append (item )
31+ elif item == ')' : # step #5
32+ while op_stack and op_stack [- 1 ] != '(' : # #5.2
33+ post_expr .append (op_stack .pop ())
34+ op_stack .pop ()
35+ else :
36+ # #4.1 and #4.2
37+ while op_stack and (op_stack [- 1 ] != '(' ) and (op_rank [item ] <= op_rank [op_stack [- 1 ]]):
38+ post_expr .append (op_stack .pop ())
39+ op_stack .append (item ) # #4.1 and #5.1
40+ while op_stack :
41+ post_expr .append (op_stack .pop ()) # #7
42+ ret = []
43+ for item in post_expr :
44+ if self .isOperand (item ):
45+ ret .append (int (item ))
46+ else :
47+ right_val = ret .pop ()
48+ left_val = ret .pop ()
49+ if item == '*' :
50+ ret .append (left_val * right_val )
51+ elif item == '/' :
52+ ret .append (left_val / right_val )
53+ elif item == '+' :
54+ ret .append (left_val + right_val )
55+ else :
56+ ret .append (left_val - right_val )
57+ return 0 if not ret else ret [0 ] # 小心全括号的场景
58+
59+ def isOperand (self , item ):
60+ return (item [0 ] >= '0' ) and (item [0 ] <= '9' )
0 commit comments