Skip to content

Instantly share code, notes, and snippets.

@fzdp
Created October 21, 2019 14:28
Show Gist options
  • Save fzdp/f187a18dae8f98d675dec8b06845e46a to your computer and use it in GitHub Desktop.
Save fzdp/f187a18dae8f98d675dec8b06845e46a to your computer and use it in GitHub Desktop.
expression evalutor in recursive way using Python
class Expression:
operator_precedence = {'+': 0, '-': 0, '*': 1, '/': 1}
operator_calculator = {
'+': lambda v1,v2 : v1 + v2,
'-': lambda v1,v2 : v1 - v2,
'*': lambda v1,v2 : v1 * v2,
'/': lambda v1,v2 : v1 / v2
}
valid_operators = ['+','-','*','/']
def __init__(self, expression):
self.expression = expression
self.operator_stack = []
self.variable_stack = []
self.expression_size = len(self.expression)
self.parsed = False
def parse(self):
i = 0
while i < self.expression_size:
i = self._parse_digit(i)
if not i:
break
i = self._parse_sub_expression(i)
if not i:
break
i = self._parse_operator(i)
i = i + 1
self.parsed = True
def _parse_digit(self, i):
k = i
while i < self.expression_size and self.expression[i].isdigit():
i = i + 1
if k != i:
self.variable_stack.append(int(self.expression[k:i]))
if i == self.expression_size:
return False
return i
def _parse_sub_expression(self, i):
if self.expression[i] == '(':
k = i
i = i + 1
remaining_right_parentheses = 1
while i < self.expression_size:
if self.expression[i] == ')':
if remaining_right_parentheses == 1:
break
else:
remaining_right_parentheses -= 1
if self.expression[i] == '(':
remaining_right_parentheses += 1
i = i + 1
sub_expr = self.expression[k + 1:i]
self.variable_stack.append(Expression(sub_expr).parse_and_get_result())
if i >= self.expression_size:
return False
return i
def _parse_operator(self, i):
current_char = self.expression[i]
if self.is_operator(current_char):
while self.operator_stack and self.get_operator_precedence(current_char) <= self.get_operator_precedence(
self.operator_stack[-1]):
operator = self.operator_stack.pop()
second_var = self.variable_stack.pop()
first_var = self.variable_stack.pop()
self.variable_stack.append(self.calculate(first_var, second_var, operator))
self.operator_stack.append(current_char)
return i
def get_result(self):
if not self.parsed:
print('You need run parse first')
return False
while self.operator_stack:
operator = self.operator_stack.pop()
second_var = self.variable_stack.pop()
first_var = self.variable_stack.pop()
self.variable_stack.append(self.calculate(first_var, second_var, operator))
return self.variable_stack.pop()
def parse_and_get_result(self):
self.parse()
return self.get_result()
@classmethod
def get_operator_precedence(cls, operator):
return cls.operator_precedence.get(operator)
@classmethod
def is_operator(cls, char):
return char in cls.valid_operators
@classmethod
def calculate(cls, var1, var2, operator):
return cls.operator_calculator.get(operator)(var1, var2)
if __name__ == '__main__':
exp_str = "9+63*2-8/2+9*2 - (98/2*67) - 23 - 4 * (5+2) + (23 * (4-2)) - (23 * (1+5))"
print('expression =',exp_str)
print(eval(exp_str))
print(Expression(exp_str).parse_and_get_result())
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment