# Share my Python solution using Reverse Polish Notation

• The idea is to convert input string into RPN. Then get the value using the result from "Evaluate Reverse Polish Notation". The speed is not fast (around 400 ms)

``````class Solution:
# @param {string} s
# @return {integer}
def calculate(self, s):
def _evalRPN(tokens):
operands = []
for token in tokens:
if token in '+-':
# meet an operator, pop operand one and two
op2, op1 = operands.pop(), operands.pop()
if token == '+':
operands.append(op1 + op2)
else:
operands.append(op1 - op2)
else:
# push operand onto stack
operands.append(int(token))
return operands[0]

# remove spaces
s = s.replace(' ', '')
index, length = 0, len(s)
operators, tokens = [], []
while index < length:
if s[index].isdigit():
# number
start = index
while index < length and s[index].isdigit():
index += 1
tokens.append(s[start : index])
else:
if s[index] in '+-':
# push top operator onto tokens if it is not open parentheses
if operators and operators[-1] != '(':
tokens.append(operators.pop())
operators.append(s[index])
elif s[index] == '(':
# push open parentheses onto stack
operators.append(s[index])
else:
# close parentheses
while operators[-1] != '(':
# push previous operators onto tokens till we meet open parentheses
tokens.append(operators.pop())
# remove open parentheses from stack
operators.pop()
index += 1

# push remaining operators onto tokens
while operators:
tokens.append(operators.pop())
# evaluate as reverse polish notation
return _evalRPN(tokens)``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.