Evaluating infix expression with brackets

Question

My assignment was to write a function that computes the value of an expression written in infix notation. We assume that we are using the four classical arithmetic operations +, -, * and / and that each binary operation is enclosed in parentheses.

My stack:

class Stack:
    def __init__(self):
        self._arr = list()
        
    def push(self, item):
        self._arr.append(item)
        #return self
    
    def pop(self):
        assert not self.is_empty(), "pop() on empty stack"
        return self._arr.pop()
    
    def is_empty(self):
        return not bool(self._arr)
    
    def peek(self):
        assert not self.is_empty(), "peek() on empty stack" 
        return self._arr[-1]
    
    def all_items(self):
        return self._arr
    
    def value_at_index(self, value):
        try:
            return self.items[value]
        except:
            return False
    
    def __len__(self):
        return len(self._arr)

The code:

def infix_brackets_eval(data):

    Stack = Stack()
    i = 0
    ret = 0
    while i < len(data):
        if data[i] != ' ':
            if data[i] not in '+-*/()':
                temp = 0
                while data[i] != ' ' and data[i]!= ')':
                    temp = temp * 10 + int(data[i])
                    i+=1
                i-=1
            elif data[i] == ')':
                B = Stack.peek()
                Stack.pop()
                x = Stack.peek()
                Stack.pop()
                A = Stack.peek()
                Stack.pop()
                if Stack.peek() == '(':
                    Stack.pop()

                if x == '-':
                    temp = A - B
                elif x == '+':
                    temp = A + B
                elif x == '*':
                    temp = A * B
                elif x == '/':
                    temp = A / B
            else:
                temp = data[i]
                #print(temp)
            Stack.push(temp)
        i += 1
    
    return Stack.peek()

infix_brackets_eval("((12 * 3) + (2 + 3) * (1 * 3))")

Output:

15

Apart from the code comments of course, could any of you point me to an example use of a tokenizer or parser? I am very curious about the application and mechanics of how to use it, in the case when the tokens are operands, tokenize also need multi-digit numbers. Unfortunately I do not know where to look. I tried to rely on various documentation but I can not translate it to this example.

Answer 1

• Python lists are stacks. I'd recommend removing the Stack class.

• You should split tokenization away from evaluation. Whilst the tokenization you need is quite simple, tokenization can get quite complicated. Not only will you shoot yourself in the foot, but the code is harder to read with tokenization and evaluation in the same function.

• Your variable names are not great.

Lets use TDD to build the tokenizer:

1. We'll handle only numbers.
   However only one character, and we'll convert to an int.

   def tokenize(text):
       for char in text:
           if char in "0123456789":
               yield int(char)
   

   >>> list(tokenize("123"))
   [1, 2, 3]
   

2. We'll handle one number of any size.
   We'll build up a 'token' stack. We'll use a list to ensure \$O(1)\$ time when adding new characters. This is because Python's strings guaranteed a minimum \$O(n)\$ time when adding.

   def tokenize(text):
       token = []
       for char in text:
           if char in "0123456789":
               token.append(char)
       if token:
           yield int("".join(token))
   

   >>> list(tokenize("1 2 3"))
   [123]
   >>> list(tokenize(""))
   []
   

3. We'll handle spaces.
   We just need to copy the if token code. And reset token after yielding one.

   def tokenize(text):
       token = []
       for char in text:
           if char in "0123456789":
               token.append(char)
           elif char in " ":
               if token:
                   yield int("".join(token))
                   token = []
       if token:
           yield int("".join(token))
   

   >>> list(tokenize("1 2 3"))
   [1, 2, 3]
   

4. We'll handle operators.
   Basically the same as spaces but we also yield the operator.

   def tokenize(text):
       token = []
       for char in text:
           if char in "0123456789":
               token.append(char)
           elif char in " +-*/()":
               if token:
                   yield int("".join(token))
                   token = []
               if char != " ":
                   yield char
       if token:
           yield int("".join(token))
   

   >>> list(tokenize("1+ 2+3"))
   [1, "+", 2, "+", 3]
   

5. Error on unknown values.
   You should error on malformed input. The hard part of programming is handling user input.

   def tokenize(text):
       token = []
       for char in text:
           if char in "0123456789":
               token.append(char)
           elif char in " +-*/()":
               if token:
                   yield int("".join(token))
                   token = []
               if char != " ":
                   yield char
           else:
               raise ValueError(f"unknown character {char!r}")
       if token:
           yield int("".join(token))
   

   >>> list(tokenize("~"))
   ValueError: unknown character '~'
   

Since we've handled the tokenization, all we need to do is use your if data[i] == ')' code.

def evaluate_infix(tokens):
    stack = []
    for token in tokens:
        if token == ")":
            lhs, op, rhs = stack[-3:]
            del stack[-3:]
            if stack[-1] == "(":
                del stack[-1]
            if op == '-':
                token = lhs - rhs
            elif op == '+':
                token = lhs + rhs
            elif op == '*':
                token = lhs * rhs
            elif op == '/':
                token = lhs / rhs
        stack.append(token)
    return stack[-1]

>>> evaluate_infix(tokenize("((12 * 3) + (2 + 3) * (1 * 3))"))
15

The hard part of programming is handling user input.

You have a bug:

>>> ((12 * 3) + (2 + 3) * (1 * 3))
51

The if stack[-1] == "(": check shouldn't be optional. A "(" should always be required. As such, your input is invalid but you've not noticed.

def evaluate_infix(tokens):
    stack = []
    for token in tokens:
        if token == ")":
            lb, lhs, op, rhs = stack[-4:]
            del stack[-4:]
            if lb != "(":
                raise ValueError("three tokens must be between parens")
            if op == '-':
                token = lhs - rhs
            elif op == '+':
                token = lhs + rhs
            elif op == '*':
                token = lhs * rhs
            elif op == '/':
                token = lhs / rhs
        stack.append(token)
    return stack[-1]

>>> evaluate_infix(tokenize("((12 * 3) + ((2 + 3) * (1 * 3)))"))
51
>>> evaluate_infix(tokenize("((12 * 3) + (2 + 3) * (1 * 3))"))
ValueError: three tokens must be between parens