原題
給一個(gè)用字符串表示的表達(dá)式數(shù)組,求出這個(gè)表達(dá)式的值台舱。
對(duì)于表達(dá)式 (2*6-(23+7)/(1+2)), 對(duì)應(yīng)的數(shù)組為:
[
"2", "*", "6", "-", "(",
"23", "+", "7", ")", "/",
(", "1", "+", "2", ")"
]
其值為 2
解題思路
- str與int相互轉(zhuǎn)化
num = int("15") // num = 15
s = str(num) // s = "15"
- 表達(dá)式 -> 建立表達(dá)式樹(shù)
- 表達(dá)式樹(shù) -> 求逆波蘭表達(dá)式
- 逆波蘭表達(dá)式 -> 求值(使用stack)奈泪。遍歷逆波蘭表達(dá)式击狮,遇到
+-*/
除pop兩個(gè)數(shù)做相應(yīng)的運(yùn)算蕊苗,結(jié)果入棧筹陵。如果遇到數(shù)字刽锤,直接push入棧
完整代碼
class expressionTreeNode:
def __init__(self, symbol):
self.symbol = symbol
self.left, self.right = None, None
class MyNode:
def __init__(self, val, s):
self.left = None
self.right = None
self.val = val
self.exp_node = expressionTreeNode(s)
class Solution:
# @param expression: a list of strings;
# @return: an integer
def get_val(self, a, base):
if a == '+' or a == '-':
return 1 + base
if a == '*' or a == '/':
return 2 + base
return sys.maxint
def create_tree(self, expression):
stack = []
base = 0
for i in range(len(expression)):
if expression[i] == '(':
if base != sys.maxint:
base += 10
continue
elif expression[i] == ')':
if base != sys.maxint:
base -= 10
continue
val = self.get_val(expression[i], base)
node = MyNode(val, expression[i])
while stack and val <= stack[-1].val:
node.left = stack.pop()
if stack:
stack[-1].right = node
stack.append(node)
if not stack:
return None
return stack[0]
def copy_tree(self, root):
if not root:
return None
root.exp_node.left = self.copy_tree(root.left)
root.exp_node.right = self.copy_tree(root.right)
return root.exp_node
def build(self, expression):
root = self.create_tree(expression)
return self.copy_tree(root)
def dfs(self, root, list):
if root == None:
return
if root.left:
self.dfs(root.left, list)
if root.right:
self.dfs(root.right, list)
list.append(root.symbol)
def convertToRPN(self, expression):
res = []
root = self.build(expression)
self.dfs(root, res)
return res
def evaluateExpression(self, expression):
reversePolishNotation = self.convertToRPN(expression)
stack = []
operators = "+-*/"
for str in reversePolishNotation:
if str not in operators:
stack.append(int(str))
else:
a = stack.pop()
b = stack.pop()
if str == "+":
stack.append(a + b)
elif str == "-":
stack.append(b - a)
elif str == "/":
stack.append(b / a)
elif str == "*":
stack.append(a * b)
if not stack:
return 0
return stack[-1]