Evaluating an expression using stack in Python

Question

I want to write a Python code that will evaluate an expression using stack. I have the following code, where numStk is a stack that holds number and optStk that holds operators. In the expression 2+3*4-6, at the end of for loop, numStack contains 2, 12, and 6; and optStk contains - and +. Now how can I make my setOps() function to pop elements from the two stacks to do the evaluate the expression?

def main():
      raw_expression = input("Enter an expression: ")
      expression = raw_expression.replace(" ", "")
      for i in expression:
          if (i in numbers):
              numStk.push(i)
          else:
              setOps(i)
              optStk.push(i)
      ## code needed to evaluate the rest of the elements in stackstack
      return valStk.top()

My setOps(i) function is as follow:

def repeatOps(refOp):
      while (len(valStk) > 1 and operators.index(refOp) <= operators.index(optStk.top())):
      x = numStk.pop()
      y = numStk.pop()
      op = optStk.pop()
      numStk.push(str(eval(x+op+y)))

cdlane · Accepted Answer · 2017-10-16 04:00:35Z

Even if I fill in all the stuff you left out, there are issues with your code: setOps() appears to be called repeatOps(); numStk is sometimes called valStk; you evaluate in the wrong order, e.g. "6-5" is evaluated "5-6"; you're calling eval()!

Below's my filling out and reworking of your code to address the above issues:

from collections import OrderedDict

DIGITS = "0123456789"

# position implies (PEMDAS) priority, low to high
OPERATORS = OrderedDict([  \
    ['+', lambda a, b: a + b], \
    ['-', lambda a, b: a - b], \
    ['*', lambda a, b: a * b], \
    ['/', lambda a, b: a / b], \
    ])

def operator_priority(character):
    return list(OPERATORS.keys()).index(character)

class Stack(list):
    """ minimalist stack implementation """

    def push(self, thing):
        self.append(thing)

    def top(self):
        return self[-1]

def evaluate(expression):
    numStk = Stack()
    optStk = Stack()

    def setOps(refOp):
        while numStk and optStk and operator_priority(refOp) <= operator_priority(optStk.top()):
            y = numStk.pop()
            x = numStk.pop()
            op = optStk.pop()
            print(x, op, y)  # debugging
            numStk.push(OPERATORS[op](x, y))

    for i in expression:
        if i in DIGITS:
            numStk.push(int(i))
        else:
            setOps(i)
            optStk.push(i)

    if optStk:
        # evaluate the rest of the elements in stacks
        setOps(list(OPERATORS.keys())[0])  # trigger using lowest priority operator

    return numStk.top()

if __name__ == "__main__":
    raw_expression = input("Enter an expression: ")
    expression = raw_expression.replace(" ", "")
    print(evaluate(expression))

Far from perfect but something to get you going:

EXAMPLE

> python3 test.py
Enter an expression: 2+3*4-6
3 * 4
12 - 6
2 + 6
8
>

To address your original question, the key to finishing the evaluation seems to be running setOps() with a fictitious, low priority operator if there's anything left in the optStk.

Collectives™ on Stack Overflow

Evaluating an expression using stack in Python

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related