Created
October 21, 2019 14:28
-
-
Save fzdp/f187a18dae8f98d675dec8b06845e46a to your computer and use it in GitHub Desktop.
expression evalutor in recursive way using Python
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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