2
\$\begingroup\$

The algorithm involves using two stacks.

One stack (call it token_stack) holds the operators (like +, - etc) and operands (like 3,4 etc) and the other stack (call it count_stack) holds the number of operands left to be seen (say 2 for binary operators).

Anytime an operator is seen, it is pushed onto the token_stack and the number of operands left to be seen for it is pushed onto the count_stack.

Anytime an operand (like 3,5 etc) is seen, the top element of the count_stack is decremented.

If the number of operands left to be seen becomes zero, the top element is popped off from the count_stack. Then from the token_stack, the number of operands required and the operator is popped off. The operation is then performed to get a new value (or operand).

Now the new operand is pushed back onto the token_stack. This new operand push causes you to take another look at the top of the count_stack and the same process is repeated (decrement the operands seen, compare with zero etc).

If the operand count does not become zero, you continue with the next token in the input.

For example, say you had to evaluate "- 10 + 7 * 2 3", the stacks will look like (left is the top of the stack):

count_stack     token_stack         Input
2               -                   10 + 7 * 2 3
1               10 -                + 7 * 2 3 
2 1             + 10 -              7 * 2 3 
1 1             7 + 10 -            * 2 3 
2 1 1           * 7 + 10 -          2 3
1 1 1           2 * 7 + 10 -        3    
0 1 1           3 2 * 7 + 10 - 

Since it has become zero, you pop off two operands, the operator * and evaluate
and push back 6. You pop 0 from the count_stack.

1 1             6 7 + 10 -

Pushing back you decrement the current count_stack top.

0 1             6 7 + 10 -

Since it has become zero, you pop off two operands, the operator + and evaluate 
and push back 13.

1               13 10 -

Pushing back you decrement the current count_stack top.

0               13 10 -

Since it has become zero, you pop off two operands, the operator - and evaluate 
and push back -3.

Since count_stack is now empty and token_stack contain the final result, return it.

Code:

#!/usr/bin/env python3

import operator
from typing import Iterable, Union

OPCODES = {
    "+": operator.add,
    "-": operator.sub,
    "*": operator.mul,
    "/": operator.truediv,
    "//": operator.floordiv,
    "%": operator.mod,
    "^": operator.pow,
    "<": operator.lt,
    "<=": operator.le,
    ">": operator.gt,
    ">=": operator.ge,
    "==": operator.eq,
    "!=": operator.ne,
}


def _eval_op(lhs: float, rhs: float, opcode: str) -> float:
    return OPCODES[opcode](lhs, rhs)


def _eval_expr(tokens: Iterable[Union[float, str]]) -> float:
    token_stack = []
    count_stack = []

    for token in tokens:
        if isinstance(token, (int, float)):
            # If the first token is an operand and there are more tokens
            # following it.
            if not token_stack and len(list(tokens)) > 1:
                raise ValueError("Invalid expression.")
            token_stack.append(token)

            if count_stack:
                count_stack[-1] -= 1
        else:
            if token in OPCODES:
                count_stack.append(2)  # Two operands left to be seen for the binary op.
            else:
                raise ValueError("Invalid operator seen.")
            token_stack.append(token)

        while count_stack and count_stack[-1] == 0:
            count_stack.pop()
            try:
                rhs = token_stack.pop()
                lhs = token_stack.pop()
                op = token_stack.pop()
                token_stack.append(_eval_op(lhs, rhs, op))
            except (ValueError, IndexError): 
                raise ValueError("Invalid expression.")
            except ZeroDivisionError:
                raise ValueError("Can not divide by zero.")
            
            if count_stack:
                count_stack[-1] -= 1

    if len(token_stack) != 1 or count_stack:
        raise ValueError("Invalid expression.")

    if token_stack:
        return token_stack.pop()
    return 0


def _tokenize_expr(expr: str) -> Iterable[Union[str, float]]:
    for token in expr.split():
        if token in OPCODES:
            yield token
        else:
            try:
                yield int(token)
            except ValueError:
                try:
                    yield float(token)
                except ValueError:
                    raise ValueError("Invalid symbol found.")


def eval_prefix_expr(expr: str):
    """
    Evaluate a prefix expression.

    Supported operators:
        - Addition (+)
        - Subtraction (-)
        - Multiplication (*)
        - Division (/)
        - Floor Division (//)
        - Modulo (%) 
        - Equality - equal to (==) 
        - Difference - not equal to (!=) 
        - Ordering: 
              1) less than (<)
              2) less than or equal to (<=)
              3) greater than (>)
              4) greater than or equal to (>=)
    """
    tokens = _tokenize_expr(expr)
    return _eval_expr(tokens)


def main() -> None:
    test_data = [
        ("34", 34),
        ("+", None),
        (" + 1 2 3", None),
        ("+ 3 4", 7),
        ("+ -3 4", 1),
        ("+ ^ 5 4 + 3 4", 632),
        ("+ 10a 29", None),
        ("/ * 10 5 + 6 2", 6.25),
        ("- 10 + 7 * 2 3", -3),
        ("icaoscasjcs", None),
        ("1038 - // * 10 5 + 7 3 2", None),
        ("", 0),
        ("$ 9 2", None),
        ("+ 3e-08 2.1", 2.10000003),
        ("+ < 1 9 9", 10),
        ("== 1 1", 1),
    ]

    for expr, res in test_data:
        expr_repr = repr(expr)
        print(f"expr: {expr_repr}", end="")
        try:
            rv = eval_prefix_expr(expr)
            assert rv == res, f"Expected: {res}, Received: {rv}"
        except Exception as e:
            rv = e
        print(f", result: {repr(rv)}")


if __name__ == "__main__":
    main()

prints:

expr: '34', result: 34
expr: '+', result: ValueError('Invalid expression.')
expr: ' + 1 2 3', result: ValueError('Invalid expression.')
expr: '+ 3 4', result: 7
expr: '+ -3 4', result: 1
expr: '+ ^ 5 4 + 3 4', result: 632
expr: '+ 10a 29', result: ValueError('Invalid symbol found.')
expr: '/ * 10 5 + 6 2', result: 6.25
expr: '- 10 + 7 * 2 3', result: -3
expr: 'icaoscasjcs', result: ValueError('Invalid symbol found.')
expr: '1038 - // * 10 5 + 7 3 2', result: ValueError('Invalid expression.')
expr: '', result: ValueError('Invalid expression.')
expr: '$ 9 2', result: ValueError('Invalid symbol found.')
expr: '+ 3e-08 2.1', result: 2.10000003
expr: '+ < 1 9 9', result: 10
expr: '== 1 1', result: True

Why did I not reverse the list of tokens and swap the operands for each operator and evaluate it like a postfix expression, which would have been way simpler? I already did that here.

Review Request:

Are there simpler ways to solve the problem?

General coding comments, style, idiomatic code, et cetera.

\$\endgroup\$

1 Answer 1

4
\$\begingroup\$

Helpful errors

You raise a couple of errors like

raise ValueError("Invalid expression.")

If I were to use your code and it gives me this error, I might be helpful if you gave me more information on what exactly is wrong here. For example raise ValueError("Invalid symbol found."): which symbol exactly?

Reduce complexity

You could reduce the complexity of your _eval_expr method by introducing a _eval_token method and using this as loop body for the for token in tokens loop.

try_parse utility function

try:
    yield int(token)
except ValueError:
    try:
        yield float(token)
    except ValueError:
        raise ValueError("Invalid symbol found.")

What about introducing a utility function try_parse (warning: untested):

T = TypeVar("T")
U = TypeVar("U")

def try_parse(value: T, *parse_functions: Callable[[T], U]) -> U:
    for parse_function in parse_functions:
        try:
            return parse_function(value)
        except ValueError:
            pass
    raise ValueError(f"Cannot parse {value} with any of {parse_functions}")

This takes a level of indentation (complexity) out of your _tokenize_expr method.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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