Question

In python: using a stack, implement a function that takes in an arithmetic expression, and evaluates it, supported operations are + and -, which have same precedence. .

Answer 1

class Stack:
  
 
  def __init__(self):
    self.stack = []
  
  # push into stack
  def push(self, data):
    if data not in self.stack:
      self.stack.append(data)
      return True
    else:
      return False
    [r]
  # remove the top element
  def pop(self):
    if len(self.stack) <= 0:
      return "Stack is empty!"
    else:
      return self.stack.pop()
    
  # returns the size of the element
  def size(self):
    return len(self.stack)
    
  # peek to see the top element
  def peek(self):
    return self.stack[-1]
    
  # to check if stck is empty
  def isEmpty(self):
    if len(self.stack) <= 0:
      return True
    else:
      return False
  
  # show the content of stack
  def show(self):
    return self.stack

def applyOp(op, var2, var1):
  if op == '+':
    return int(var1) + int(var2)
  elif op == '-':
    return int(var1) - int(var2)
  else:
    return 0

# check for precedence of operators
# returns True if op2 has higher precedence than op1
def hasPrecedence(op1, op2):
  if op2 == '(' or op2 == ')':
    return False
  elif (op2 == '+' or op2 == '-'):
    return False
  else:
    return True


expr = raw_input("Enter the expression:")


tokens = map(str, expr)

tokens = ' '.join(tokens).split()


var = Stack()

ops = Stack()

skip = 0
for i in range(len(tokens)):

  if skip >= 1:
    
    skip -= 1
    continue

  if tokens[i] >= '0' and tokens[i] <= '9':
    num = tokens[i]
    
    for j in range(i+1, len(tokens)):
      if tokens[j] >= '0' and tokens[j] <= '9':
        num = num + tokens[j]
        skip += 1
      else:
        break
    
    var.push(num)
    print(var.show())
  
 
  elif tokens[i] == '(':
    
    ops.push(tokens[i])
  
  
  elif tokens[i] == ')':
    print("Encountered closing parenthesis...")
    while ops.peek() != '(':
      
      value = applyOp(ops.pop(), var.pop(), var.pop())
      if(value == "infinity"):
        print("Invalid Expression")
        break
      else:
        print(value)
        var.push(value)
    ops.pop()
  
  elif tokens[i] in ('+','-'):
    while ops.isEmpty() is False and hasPrecedence(tokens[i], ops.peek()):
      x = applyOp(ops.pop(), var.pop(), var.pop())
      print(x)
      var.push(x)
  
    ops.push(tokens[i])
    print(ops.show())

while(ops.isEmpty() is False):
  var.push(applyOp(ops.pop(), var.pop(), var.pop()))
print("Result of the expression is " + str(var.pop()))