1
\$\begingroup\$

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.

\$\endgroup\$
3
  • 3
    \$\begingroup\$ Are you KermitTheFrog? Because your Stack is almost exactly the same as in Kermit's question \$\endgroup\$
    – Peilonrayz
    Nov 17 at 22:24
  • \$\begingroup\$ well... we are classmates \$\endgroup\$ Nov 17 at 22:59
  • \$\begingroup\$ And now we r both struggling with your comment about parsing/tokenizer @Peilonrayz :D \$\endgroup\$ Nov 17 at 23:00
2
\$\begingroup\$
  • 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
\$\endgroup\$
2
  • \$\begingroup\$ What variables names i should use in this case? What would be more "proffesional"? \$\endgroup\$ Nov 18 at 9:44
  • \$\begingroup\$ @TheUselessProgrammer4 I've renamed a number of your variables. A-> lhs, B -> rhs, x -> op, temp -> token. Your names can mean anything, where the names I've picked say what the variables contain. \$\endgroup\$
    – Peilonrayz
    Nov 18 at 18:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.