Created
February 23, 2016 17:31
-
-
Save v-kolesnikov/660a44f480103fa57f47 to your computer and use it in GitHub Desktop.
This file contains 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
#!/usr/bin/env python3 | |
# -*- coding: utf-8 -*- | |
from enum import IntEnum, unique | |
@unique | |
class Priority(IntEnum): | |
Lowest = 0 | |
Low = 1 | |
Average = 2 | |
High = 3 | |
VeryHigh = 4 | |
operators = { | |
'!': {'priority': Priority.VeryHigh, 'arity': 1}, | |
'^': {'priority': Priority.High, 'arity': 2}, | |
'*': {'priority': Priority.Average, 'arity': 2}, | |
'/': {'priority': Priority.Average, 'arity': 2}, | |
'+': {'priority': Priority.Low, 'arity': 2}, | |
'-': {'priority': Priority.Low, 'arity': 2}, | |
'(': {'priority': Priority.Lowest, 'arity': 2}, | |
')': {'priority': Priority.Lowest, 'arity': 2} | |
} | |
def priority(op): | |
"""Return priority of operator $op as int.""" | |
return int(operators[op]['priority']) | |
def checkBrackets(exp): | |
"""Check brackets into expression $exp.""" | |
brackets = { | |
'(': ')', | |
'[': ']', | |
'{': '}' | |
} | |
bracketsOut = [brackets[br] for br in brackets] | |
stack = [] | |
for char in exp: | |
if char in brackets: | |
stack += char | |
elif char in bracketsOut: | |
if stack and brackets[stack[-1]] == char: | |
stack.pop() | |
else: | |
return False | |
return not stack | |
def toExpression(text): | |
"""Return expression from text as list.""" | |
exp = [] | |
num = '' | |
var = '' | |
unaryNext = True | |
for char in text: | |
if char.isdigit(): | |
num += char | |
else: | |
if num: | |
exp.append(int(num)) | |
num = '' | |
unaryNext = False | |
if char.isalpha(): | |
var += char | |
elif var: | |
exp.append(var) | |
var = '' | |
unaryNext = False | |
if char in operators: | |
if unaryNext: | |
if char == '-': | |
char = '!' | |
exp += char | |
unaryNext = True if char != ')' else False | |
if num: | |
exp.append(int(num)) | |
if var: | |
exp.append(var) | |
return exp | |
def evaluate(operands, operator): | |
""""Returns the value of the operation applied to operands.""" | |
arity = operators[operator]['arity'] | |
if len(operands) != arity: | |
print('Error: wrong count operands for operator {op}.' | |
'Expected {expected} args, three is a {three}.'.format( | |
op=operator, | |
expected=arity, | |
three=len(operands) | |
)) | |
return None | |
if operator == '^': | |
return operands[0] ** operands[1] | |
elif operator == '*': | |
return operands[0] * operands[1] | |
elif operator == '/': | |
return operands[0] / operands[1] | |
elif operator == '+': | |
return operands[0] + operands[1] | |
elif operator == '-': | |
return operands[0] - operands[1] | |
elif operator == '!': | |
return -operands[0] | |
else: | |
return None | |
def calculateRPN(exp): | |
stack = [] | |
for token in exp: | |
if isinstance(token, int): | |
stack.append(token) | |
elif token in operators: | |
arity = operators[token]['arity'] | |
operands = [stack.pop() for i in range(arity)][::-1] | |
stack.append(evaluate(operands, token)) | |
return stack.pop() | |
def toRPN(exp): | |
"""Return expression in reverse Polish notation (RPN). | |
The complexity of the algorithm O(n).""" | |
out = [] | |
stack = [] | |
for token in exp: | |
if token in operators: | |
if token == '(': | |
stack += token | |
elif token == ')': | |
while stack and stack[-1] != '(': | |
out += stack.pop() | |
if not stack: | |
print('Error: expected `(`') | |
else: | |
stack.pop() | |
else: | |
while stack and (operators[stack[-1]]['arity'] > 1 and priority(token) <= priority(stack[-1]) or | |
operators[stack[-1]]['arity'] == 1 and priority(token) < priority(stack[-1])): | |
out += stack.pop() | |
stack += token | |
else: | |
out.append(token) | |
while stack: | |
if stack[-1] == '(': | |
print('Error: expected `)`') | |
out += stack.pop() | |
return out | |
def calculateInfix(exp): | |
"""Returns the calculated value of the infix expression. | |
This function evaluates the expression in a single pass | |
using reverse polish notation and two stacks. | |
The complexity of the algorithm O(n).""" | |
out = [] | |
stack = [] | |
def calcLast(): | |
operator = stack.pop() | |
arity = operators[operator]['arity'] | |
operands = [out.pop() for i in range(arity)][::-1] | |
out.append(evaluate(operands, operator)) | |
for token in exp: | |
if token in operators: | |
if token == '(': | |
stack += token | |
elif token == ')': | |
while stack and stack[-1] != '(': | |
calcLast() | |
if not stack: | |
print('Error: expected `(`') | |
else: | |
stack.pop() | |
else: | |
while stack and (operators[stack[-1]]['arity'] > 1 and priority(token) <= priority(stack[-1]) or | |
operators[stack[-1]]['arity'] == 1 and priority(token) < priority( | |
stack[-1])): | |
calcLast() | |
stack += token | |
else: | |
out.append(token) | |
while stack: | |
if stack[-1] == '(': | |
print('Error: expected `)`') | |
calcLast() | |
return out.pop() | |
def main(): | |
print('This programm calculate expression.\n') | |
def test(): | |
dataset = [ | |
{'exp': '10^2 + 20', 'val': 120}, | |
{'exp': '(1+2) * 4 + 3', 'val': 15}, | |
{'exp': '-10 + 20 - (-3 + 5) * 3', 'val': 4}, | |
{'exp': '-10 + -10', 'val': -20}, | |
{'exp': '-10 - -10', 'val': 0}, | |
{'exp': '1.5 + 2', 'val': 3.5}, | |
{'exp': '10^2+20', 'val': 120}, | |
] | |
for case in dataset: | |
exp = toExpression(case['exp']) | |
print('Test case:\n' | |
'\tInput: {input}\n' | |
'\tParse: {parse}\n' | |
'\tCheck: {check}\n' | |
'\tValue: {value}\n'.format( | |
input=case['exp'], | |
parse=' '.join(str(i) for i in exp), | |
check=case['val'], | |
value=calculateInfix(exp) | |
)) | |
if __name__ == '__main__': | |
main() | |
test() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment