#599 · Stacks and queues · Intermediate · 70 XP · about 15 min
In postfix notation each operator comes after the two numbers it works on: 3 4 + means 3 + 4, and 2 3 4 * + means 2 + 3 * 4. A stack works it out: push numbers, and at an operator pop two numbers, combine them and push the result.
Write evaluate_postfix(expression) where expression is a string of tokens separated by spaces. A token is a whole number (it may be negative, like -3) or one of +, -, * and /. The first number popped is the right-hand side, so 8 2 - is 8 - 2. Division is ordinary division with /, so the result can be a float such as 2.5.
Return the value of the expression, or the string 'Error' when it cannot be worked out:
evaluate_postfix('2 3 4 * +') # returns 14 evaluate_postfix('5 1 2 + 4 * + 3 -') # returns 14 evaluate_postfix('7 2 /') # returns 3.5 evaluate_postfix('1 +') # returns 'Error' evaluate_postfix('1 2') # returns 'Error'
expression has at most 10,000 tokens.First solves only, ranked by stars and then time.