Reverse Polish Notation (RPN) Calculator

Question

I am trying to solve a codewar challenge (link):

Your job is to create a calculator which evaluates expressions in Reverse Polish notation.

For example expression 5 1 2 + 4 * + 3 - (which is equivalent to 5 + ((1 + 2) * 4) - 3 in normal notation) should evaluate to 14.

For your convenience, the input is formatted such that a space is provided between every token.

Empty expression should evaluate to 0.

Valid operations are +, -, *, /.

You may assume that there won't be exceptional situations (like stack underflow or division by zero).

I have 2 problems, the first is that the code looks awful and I don't know how to improve it tbh, I also want this code to be able to compute multiple digit numbers and i feel like i need to start from scratch if I want to add that.

Note : This is my first time writing a question so if there's anything wrong with it please tell me and I'll change it.

def calc(expr):
    stack = []
    for i in range(len(expr)):
        if expr[i].isdigit():
            stack.append(expr[i])
        if expr[i-1] == '.':
            stack.pop() 
        if expr[i] == '.':
            stack.pop()
            stack.append(expr[i-1] +  expr[i] + expr[i+1])
        if expr[i] == '+':
            stack.append(float(stack[-2]) + float(stack[-1]))
            for i in range(2):
                del stack[-2] 
        if expr[i] == '-':
            stack.append(float(stack[-2]) - float(stack[-1]))
            for i in range(2):
                del stack[-2]
        if expr[i] == '*':
            stack.append(float(stack[-2]) * float(stack[-1]))
            for i in range(2):
                del stack[-2]
        if expr[i] == '/':
            stack.append(float(stack[-2]) / float(stack[-1]))
            for i in range(2):
                del stack[-2]
    if stack == []:
        return 0
    else:
        return float(stack[0])

Welcome to Code Review. Your question is fine: there's a link to the relevant task, a short introduction, a piece of code that is ready to be pasted into an IDE, that's almost all one can ask. As a bonus, you could add a few example expressions next time, that's a thing that is often missing in questions. Other than that, well done. :) — Roland Illig
– Roland Illig, Commented Dec 10, 2019 at 21:54

RomanPerekhrest · Accepted Answer · 2019-12-10 21:58:44Z

11

The initial approach is full of redundant if conditions for capturing float numbers and duplicated set of statements (stack.append, for loop, del ...) for all 4 arithmetic operations.

The whole idea is achievable with a single traversal facilitated by operator (provides convenient equivalents of mathematical operations) and ast.literal_eval feature (to evaluate both int and float types):

import operator
from ast import literal_eval

math_operators = {'+': operator.add, '-': operator.sub, 
                  '*': operator.mul, '/': operator.truediv}


def calc(expr):
    tokens = expr.split()
    res = []
    for t in tokens:
        if t in math_operators:
            res[-2:] = [math_operators[t](res[-2], res[-1])]
        else:
            res.append(literal_eval(t))

    return res[0] if res else 0

Test cases:

exp = '5 1 2 + 4 * + 3 -'
print(calc(exp))   # 14

exp = '5.5 10.6 -'
print(calc(exp))   # -5.1

exp = ''
print(calc(exp))   # 0

answered Dec 10, 2019 at 21:58

RomanPerekhrest

5,3371 gold badge10 silver badges21 bronze badges

\$\begingroup\$ Just to make sure I understand both solutions, you could have stack.append(math_operators[t](stack.pop(), stack.pop()) if t in math_operators else literal_eval(t)) ? \$\endgroup\$

JollyJoker
– JollyJoker

2019-12-11 09:48:46 +00:00
Commented Dec 11, 2019 at 9:48
\$\begingroup\$ Ah, no, the order is wrong for subtraction and division then \$\endgroup\$

JollyJoker
– JollyJoker

2019-12-11 10:03:11 +00:00
Commented Dec 11, 2019 at 10:03
\$\begingroup\$ stack.append(math_operators[t](stack.pop(-2), stack.pop()) if t in math_operators else literal_eval(t)) learned something new :) \$\endgroup\$

JollyJoker
– JollyJoker

2019-12-11 11:10:48 +00:00
Commented Dec 11, 2019 at 11:10

Add a comment |

RootTwo · Accepted Answer · 2019-12-11 01:37:36Z

The challenge says the items in the expression are already separated by spaces. So, use str.split() to parse the expression.

The if statements are mutually exclusive, so use if ... elif ...

When evaluating an RPN expression, one generally pop's the arg off the stack, applies an operation, and then pushes the result.

def calc(expr):
    stack = []

    for token in expr.split():

        if token[0].isdigit():
            if '.' in token:
                stack.append(float(token))
            else:
                stack.append(int(token))

        elif token == '+':
            right_arg = stack.pop()
            left_arg = stack.pop()

            stack.append(left_arg + right_arg)

        elif token == '-':
            right_arg = stack.pop()
            left_arg = stack.pop()

            stack.append(left_arg - right_arg)

        ... same for '*' and '/' ...

    if stack == []:
        return 0
    else:
        return stack.pop()

Roland Illig · Accepted Answer · 2019-12-11 09:19:23Z

2

(Update: as stated in the comment, the codewars task explicitly demands that an empty expression is to return 0. This makes my following remarks invalid for this particular task. In all other situations they still apply.)

There's one thing that you should do in the last lines of your code:

    if stack == []:
        return 0
    else:
        return float(stack[0])

The task explicitly says that you may assume the input is error-free and that your program may do whatever it wants on erroneous input. You currently ignore the error and silently return a wrong result (0). You should not do that.

Instead you should just write:

    return stack[0]

The stack is assumed to only contain floats. Therefore it is not necessary to convert the float to a float again. If you want to check it explicitly:

    assert stack[0] == float(stack[0])
    return stack[0]

Trying to return the result from an empty stack should result in an exception. That way you know for sure that there was something wrong. That's much better than continuing the calculation with a wrong result.

edited Dec 11, 2019 at 9:19

answered Dec 10, 2019 at 22:00

Roland Illig

21.9k2 gold badges36 silver badges83 bronze badges

3

\$\begingroup\$ The problem explicitly states an empty expression should return 0, so the OP is not ignoring an error and silently returning a wrong result. It is in fact doing the right thing. \$\endgroup\$

AJNeufeld
– AJNeufeld

2019-12-11 05:44:29 +00:00
Commented Dec 11, 2019 at 5:44
\$\begingroup\$ Several hours later I noticed that the task says an empty expression instead of an empty result. Therefore it might still be better to handle the special case of an empty expression at the top (together with a helpful comment), and to throw an exception at the bottom. \$\endgroup\$

Roland Illig
– Roland Illig

2019-12-11 22:43:34 +00:00
Commented Dec 11, 2019 at 22:43

Add a comment |

JollyJoker · Accepted Answer · 2019-12-11 12:46:55Z

1

A simple solution using eval().

As others have done, use the result as a stack and pop the numbers if the token is an operator. The eval converts from string to numbers, handling floats as well.

def calc(expr):
    res = []
    for t in expr.split():
        if t in '+-*/':
            t = str(res.pop(-2)) + t + str(res.pop())
        res.append(eval(t))
    return res[0] if res else 0

exp = '5 1 2 + 4 * + 3 -'
print(calc(exp))   # 14

Try it online!

edited Dec 11, 2019 at 12:46

answered Dec 11, 2019 at 11:57

JollyJoker

8414 silver badges10 bronze badges

Add a comment |

Stack Exchange Network

Reverse Polish Notation (RPN) Calculator

4 Answers 4

You must log in to answer this question.

Hot Network Questions

Reverse Polish Notation (RPN) Calculator

4 Answers 4

You must log in to answer this question.

Related

Hot Network Questions