Skip to content

Instantly share code, notes, and snippets.

@saraswatmks
Last active May 18, 2019 12:46
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save saraswatmks/4c79d8bb1b441bc2e8d51518a8ddd79d to your computer and use it in GitHub Desktop.
Save saraswatmks/4c79d8bb1b441bc2e8d51518a8ddd79d to your computer and use it in GitHub Desktop.
Evaluate expression with infix operators in Python
from functools import reduce
def inifix_operator(expression, variables=None):
opr = set(['/','+','-','*'])
ex = expression.strip().split()
num_count = len(opr.difference(ex))
num_opr = len(opr.intersection(ex))
valid = num_count - num_opr
if valid != 1:
print("nothing")
stack = []
for i in ex[::-1]:
print(i)
# if i is a number
if i.isdigit():
stack.append(i)
print(stack)
else:
# operand found
if i == '+':
stack = stack[:-2] + [sum([int(x) for x in stack[-2:][::-1]])]
print(stack)
elif i == '*':
stack = stack[:-2] + [reduce(lambda x,y: x*y, [int(x) for x in stack[-2:][::-1]])]
print(stack)
elif i == '-':
stack = stack[:-2] + [reduce(lambda x,y: x-y, [int(x) for x in stack[-2:][::-1]])]
print(stack)
elif i == '/':
stack = stack[:-2] + [reduce(lambda x,y: x//y, [int(x) for x in stack[-2:][::-1]])]
print(stack)
print(stack)
if __name__ == '__main__':
sample1 = "+ 6 * - 4 + 2 3 8"
sample2 = "+ 3 8"
inifix_operator(d_small)
inifix_operator(d)
@saraswatmks
Copy link
Author

Note: The complexity of this solution is O(n). It works the following way:

  1. Reverses the input string.
  2. Append numbers to the stack until a operator is found.
  3. As soon as the operator is found, it takes the last 2 numbers from the last, reverses them and makes computation. For example:
    [2,3,4,'+'] will become [2, 7] as the new list.
  4. Repeat this logic for all operators.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment