18 votes

Programming Challenge: Reverse Polish Notation Calculator

It's been nearly a week, so it's time for another programming challenge!

This time, let's create a calculator that accepts reverse Polish notation (RPN), also known as postfix notation.

For a bit of background, RPN is where you take your two operands in an expression and place the operator after them. For example, the expression 3 + 5 would be written as 3 5 +. A more complicated expression like (5 - 3) x 8 would be written as 5 3 - 8 x, or 8 5 3 - x.

All your program has to do is accept a valid RPN string and apply the operations in the correct order to produce the expected result.

10 comments

  1. jzimbel
    (edited )
    Link
    JavaScript, ES6: (...I might be overusing the destructuring operator just a tiny bit) // just used for printing each evaluation step to console, not necessary for the solution const withLogging =...

    JavaScript, ES6:
    (...I might be overusing the destructuring operator just a tiny bit)

    // just used for printing each evaluation step to console, not necessary for the solution
    const withLogging = func => (...args) => {
      console.log(...args.slice(0, 2));
      return func(...args);
    };
    
    const operators = {
      '+': (x, y) => x + y,
      '-': (x, y) => x - y,
      '/': (x, y) => x / y,
      x: (x, y) => x * y,
      '*': (x, y) => x * y
    };
    
    const rpnReducer = (values, item) =>
      operators[item]
        ? [...values.slice(0, -2), operators[item](...values.slice(-2))]
        : [...values, +item];
    
    // pass `true` as second argument to see all the evaluation steps :D
    const rpnEvaluate = (rpnExpression, logSteps = false) =>
      rpnExpression
        .split(' ')
        .reduce(logSteps ? withLogging(rpnReducer) : rpnReducer, [])[0];
    
    rpnEvaluate('15 7 1 1 + - / 3 * 2 1 1 + + -', true);
    

    Pop open your browser dev tools and paste the whole thing in to try it out. 😎

    6 votes
  2. [2]
    cge
    (edited )
    Link
    As I find these sorts of challenges most interesting when trying to come up with a solution that does not take the obvious approach, here is my first attempt (in Python). Amongst other features:...

    As I find these sorts of challenges most interesting when trying to come up with a solution that does not take the obvious approach, here is my first attempt (in Python). Amongst other features:

    • It flexibly chooses between ints, floats, and complex numbers (if entered as, eg, "2 3.2j +").
    • It does not use a stack (note, because of how python lists work, this has horrible time complexity).
    • It should pass any test with valid inputs, but
    • with invalid inputs, it allows arbitrary code execution (for example, input of "3 4 +bool(open('amaliciouslyplacedfile','w').write('thisisbad'))+")
    def rpneval(s):
        s=s.split(' ')
        i=0
        while i<len(s):
            try:
                complex(s[i])
                i+=1
            except:
                s[i-2]=eval(('{}'*3).format(s[i-2],s[i],s[i-1]))
                del(s[i-1]); del(s[i-1])
                i-=1
        return s[-1]
    
    6 votes
    1. Emerald_Knight
      Link Parent
      "Does not use a stack" could be debatable if we want to consider the list of tokens a pre-loaded stack that you're operating on. But that's just being pedantic. Interesting solution! Disgusting...

      "Does not use a stack" could be debatable if we want to consider the list of tokens a pre-loaded stack that you're operating on. But that's just being pedantic.

      Interesting solution! Disgusting with your arbitrary code execution and exception-oriented functionality, but interesting!

      2 votes
  3. cge
    Link
    With apologies for giving two completely different answers, here is another version, with an entirely different approach. Here, I parse the token list backward, using recursive function calls....

    With apologies for giving two completely different answers, here is another version, with an entirely different approach. Here, I parse the token list backward, using recursive function calls. Rather than returning a number, I return a list.

    • For valid RPN strings, defined as strings where, processed normally, every operator acts on two numbers, npr returns the correct answer. However, it only does as many operations as it needs to do in order to find that answer. Any operators that weren't used in the final answer aren't applied (eg, "1 1 + 2 3 *" will only apply one multiplication operation).
    • For incomplete RPN strings, defined as strings where, processed normally, every operator does not have two numbers to operate on, npr does as many operations as necessary to find, if possible, a number as the last item (like an RPN calculator that has ignored any errors and cleared the stack whenever an error took place), while returning a reduced, incomplete RPN token list. The reduced list contains operations and numbers that are equivalent, however, to the input string.
    • Why is this interesting? Because substrings of valid RPN strings are, in general, either valid or incomplete RPN strings. Thus, for a string A, if it is split into a list of arbitrary substrings S_i, then npr(A) = npr( concatenation of every npr(S_i)). So, for example:
    npr('15 7 1 1 + - / 3 * 2 1 1 + + -') == npr(npr('15 7 1 1 + -') + npr('/ 3 * 2 1 1 + + -'))
    

    Of course, the actual motivation of this was just to do RPN starting from the end of the string.

    applyop =  {'+': lambda x, y: x + y, '-': lambda x, y: x - y, 
                '*': lambda x, y: x * y, '/': lambda x, y: x / y}
    isop = lambda x: x in applyop.keys()
    def npr(l):
        if isinstance(l, str):
            l = l.split(' ')
        if not isop(l[-1]):
            return l
        if len(l) < 2:
            return l
        if isop(l[-2]):
            l = npr(l[:-1])+l[-1:]
        if len(l) < 3:
            return l
        if isop(l[-3]):
            l = npr(l[:-2])+l[-2:]
        if not (isop(l[-2]) or isop(l[-3])):
            return l[:-3] + [applyop[l[-1]](float(l[-3]),float(l[-2]))]
        return l
    
    5 votes
  4. s4b3r6
    Link
    When it comes to these challenges, I try to push myself, by reaching for something I'm not entirely familiar with, or by making it as performant as I can, or codegolf to get the least bytes, etc....

    When it comes to these challenges, I try to push myself, by reaching for something I'm not entirely familiar with, or by making it as performant as I can, or codegolf to get the least bytes, etc.

    Unfortunately, almost all of those answered by an RPN on D's main website, and is a fantastic piece of code.

    I'm not more creative than that blend of mixins, static loops, and Ds robust IO.

    So, the only real choice I have left... Is completeness.

    Parsing an RPN is braindead simple - split by whitespace, evaluate left to right, if not an operator, push ot the stack. By being clever you can do other things, and increase your performance... But I'm not interested in that this time around.

    So, the goal is:

    • A stack for storing numbers and results
    • + an addition operator
    • - a minus operator
    • * a multiplication operator
    • / a divide operator
    • i/ integer division operator
    • √ a square root operator
    • ^ an exponent operator
    • % a modulus operator
    • ][ a clamp operator
    • .. a rounding operator

    First up!

    Our braindead parser:

    local parser = function(data)
      -- File handling can happen elsewhere. We just want the data.
      assert(type(data) == "string")
      -- Here it comes, the whole thing:
      return string.gmatch(example, "%S+")
    end
    

    Here, we use Lua's inbuilt regex to split apart a string based on any whitespace.

    There are some caveats.

    • Lua can only return a few thousand values. It's note infinitely scaleable.
    • This just gives us string token, without attempting to do any types

    We'll leave the parser for now, but I do plan to come back to it.

    Instead, let's build our operators, and assume we've worked out parser and made a stack (implemented as a simple table).

    local add = function(stack)
      local a = table.remove(stack) or 0
      local b = table.remove(stack) or 0
      stack[#stack + 1] = a + b
    end
    

    By using Lua's ability to do comparisons wherever you feel like, we can add some data protection here.

    table.remove is also a helpful little thing. It returns the last value in a table, removing it, or returns nil.


    So, now we can whack out a few functions.

    I'll gloss over most.

    But! We do need to worry about our pesky little division operator.

    Because, well, division by zero should return an infinite number, positive or negative. Lua, being little more than C in ways of the stdlib, doesn't know what the hell an infinite value is. And I don't really feel like adding a type, which is actually quite a pain in the butt.

    Instead, let's opt for an older way computers used to handle division by zero, not with a crash error, or with an infinite value, or a NotANumber, but with a zero. Negative zero, to be more precise.

    It's unusual, and users need to be aware of it, but it does have a history in the world of computer science.

    local divide = function(stack)
      local a = table.remove(stack) or 0
      local b = table.remove(stack) or 0
      if b == 0 then
        stack[#stack + 1] = -0
      else
        stack[#stack + 1] = a / b
      end
    end
    

    And of course, implementing integer division is also nice and simple:

    local divide_int = function(stack)
      divide(stack)
      stack[#stack + 1] = math.ceil(table.remove(stack))
    end
    

    The only other interesting operator will probably be clamp.

    Clamping is something that often turns up in video programming. You take three numbers, sort them smallest to largest, and take the middle one and discard the rest.

    It's actually quite useful, and interesting for us because it takes three arguments, instead of two, demonstrating flexibility.

    local clamp = function(stack)
      local t = {table.remove(stack), table.remove(stack), table.remove(stack)}
      if #t == 3 then
        table.sort(t)
        stack[#stack + 1] = t[2]
      elseif #t == 2 then
        if t[1] > t[2] then
          stack[#stack + 1] = t[1]
        else
          stack[#stack + 1] = t[2]
        end
      else
        stack[#stack + 1] = t[1] or 0
      end
    end
    

    So... What was simple, when accounting for edge cases, looks nuts.

    At it's core, when three args can be pulled off the stack, it sorts them and returns the middle.

    However, if only two can, then it returns the larger of the two.

    If one can, it returns that one.

    Finally, if none can, then it returns zero.

    Technically, clamp requires three and shouldn't be so flexible, but it's nice in a calculator if it doesn't explode every time you try and do something. Which also let's you come up with some stupid little tricks here and there.

    Note: We probably need to define how our intended .. or rounding function works. We'll use math.ceil, so it rounds up.


    Let's get back to the parser.

    We basically need to do two things, turn strings that might be numbers into numbers, and link symbol representations with our functions.

    First, numbers are easy.

    local parser = function(data)
      -- File handling can happen elsewhere. We just want the data.
      assert(type(data) == "string")
      local t = {}
      for atom in string.gmatch(example, "%S+") do
        if tonumber(atom) then
          t[#t +1] = tonumber(atom)
        else
          -- TODO: Link in our functions.
        end
      end
    end
    

    And linking in our functions is dead simple too, as we have first class functions, and UTF-8 strings.

    local parser = function(data)
      -- File handling can happen elsewhere. We just want the data.
      assert(type(data) == "string")
      local t = {}
      for atom in string.gmatch(example, "%S+") do
        if tonumber(atom) then
          t[#t + 1] = tonumber(atom)
        elseif atom == '+' then
          t[#t + 1] = add
        elseif atom == '-' then
          t[#t + 1] = minus
        elseif atom == '*' then
          t[#t + 1] = multiply
        elseif atom == '/' then
          t[#t + 1] = divide
        elseif atom == 'i/' then
          t[#t + 1] = divide_int
        elseif atom == '√' then
          t[#t + 1] = square_root
        elseif atom == '^' then
          t[#t + 1] = exponent
        elseif atom == '%' then
          t[#t + 1] = mod
        elseif atom == '][' then
          t[#t + 1] = clamp
        elseif atom == '..' then
          t[#t + 1] = round
        end
      end
      t = reverse(t)
      return t
    end
    

    Note: Technically, we could have used the symbol names when defining the functions. But the syntax gets a bit more cluttered.


    So, we have all our functions that play with our stack, safely. Unless something erratic happens, the calculator won't crash. And if it does crash, you probably have worse things on your hands.

    To make the calculator work, all we have left is an evalulator, and then cli bindings (which I won't go into).

    The evaluator takes the parse tree, (array really... it's a stack), and goes through it.

    local eval = function(tbl)
      local stack = {}
      while #tbl > 0 do
        local x = table.remove(tbl)
        -- Use the operator if it was
        if type(x) == "function" then
          x(stack)
        -- Ignore x if it was a nil for some weird reason
        elseif x then
          stack[#stack + 1] = x
        end
      end
      if #stack > 0 then
        print(stack[#stack])
      end
    end
    

    We end our evaluator with a little print statement of the top of the stack, so that the calculator feels useful.


    I've glossed over a few things, and not really expanded it, because it tends to be simple, but you can find my complete implementation here.

    5 votes
  5. bhrgunatha
    Link
    Basic Racket with no fancy eval or macro nonsense or error handling! #lang racket (define operators `((,"+" . ,+) (,"-" . ,-) (,"*" . ,*) (,"/" . ,/))) ;; String -> Number (define (evaluate...

    Basic Racket with no fancy eval or macro nonsense or error handling!

    #lang racket
    
    (define operators `((,"+" . ,+)
                       (,"-" . ,-)
                       (,"*" . ,*)
                       (,"/" . ,/)))
    
    ;; String -> Number
    (define (evaluate expression)
      (first
       (for/fold [(result null)]
                 ([token (string-split expression)])
         (define operator (assoc token operators))
         (if operator
             (cons ((cdr operator) (second result) (first result))
                   (drop result 2))
             (cons (string->number token) result)))))
    
    (module+ test
      (require rackunit)
      (check-eq? (evaluate "1") 1)
      (check-eq? (evaluate "2 2 +") 4)
      (check-eq? (evaluate "3 3 *") 9)
      (check-eq? (evaluate "5 4 -") 1)
      (check-eq? (evaluate "6 3 /") 2)
      (check-eq? (evaluate "2 2 + 2 *") 8)
      (check-eq? (evaluate "3 3 3 * +") 12)
      ; https://en.wikipedia.org/wiki/Reverse_Polish_notation#Example
      (check-eq? (evaluate "15 7 1 1 + - / 3 * 2 1 1 + + -") 5)
      )
    
    4 votes
  6. cmh
    (edited )
    Link
    A C++17 version - with constexpr compile time support. Slightly hacky fixed size stack to allow compile time generation. Expects completely valid input. #include <string_view> #include <cstdio.h>...

    A C++17 version - with constexpr compile time support. Slightly hacky fixed size stack to allow compile time generation. Expects completely valid input.

    #include <string_view>
    #include <cstdio.h>
    
    //from_chars isn't constexpr for standard reasons
    constexpr void from_chars_local(const char *s, const char *t, int &x) {
    	x = 0;
    	while (s != t) {
    		x = x * 10 + *s - '0';
    		s++;
    	}
    }
    
    constexpr int eval_rpn(const std::string_view &s) {
    	int stack[128] = {};
    	int sind = 0;
    
    	std::string_view::size_type i = 0, j = 0;
    	
    	while (i != s.size()) {
    		switch (s[i]) {
    		case '+':
    			stack[sind - 2] = stack[sind - 2] + stack[sind - 1]; sind -= 1;
    			break;
    		case '-':
    			stack[sind - 2] = stack[sind - 2] - stack[sind - 1]; sind -= 1;
    			break;
    		case '*':
    			stack[sind - 2] = stack[sind - 2] * stack[sind - 1]; sind -= 1;
    			break;
    		case '/':
    			stack[sind - 2] = stack[sind - 2] / stack[sind - 1]; sind -= 1;
    			break;
    		case ' ':
    			break; // can't i+=2 in constexpr
    		default:
    			j = s.find_first_of(' ', i);
    			from_chars_local(&s[i], &s[j], stack[sind++]);
    		}
    
    		i = i>j ? i + 1 : j + 1;
    	}
    
    	return stack[0];
    }
    
    int main()
    {
            static_assert(eval_rpn("15 7 1 1 + - / 3 * 2 1 1 + + -") == 5)
    }
    
    4 votes
  7. Emerald_Knight
    (edited )
    Link
    Here's my own, once again in PHP: <?php class ReversePolishNotationCalculator { public function __construct() { // Empty. } private function validateExpression($expression) { $tokens = explode('...

    Here's my own, once again in PHP:

    <?php
    class ReversePolishNotationCalculator {
        public function __construct() {
            // Empty.
        }
        
        private function validateExpression($expression) {
            $tokens = explode(' ', $expression);
            
            $numbers = 0;
            $operators = 0;
            foreach($tokens as $token) {
                if(preg_match('/^\d+(\.\d+)?$/', $token)) {
                    $numbers++;
                } else if(preg_match('/^[\+\-\/x]$/', $token)) {
                    $operators++;
                } else {
                    return false;
                }
                
                if($operators >= $numbers) {
                    return false;
                }
            }
            
            return $operators == ($numbers - 1);
        }
        
        private function evaluate(&$tokens) {
            $operator = array_shift($tokens);
            if(preg_match('/^\d+(\.\d+)?$/', $operator)) {
                return doubleval($operator);
            }
            
            $left_result = $this->evaluate($tokens);
            $right_result = $this->evaluate($tokens);
            
            switch($operator) {
                case '+':
                    return $right_result + $left_result;
                case '-':
                    return $right_result - $left_result;
                case '/':
                    return $right_result / $left_result;
                case 'x':
                    return $right_result * $left_result;
                default:
                    throw new Exception('Operator "' . $operator . '" not recognized.');
            }
        }
        
        public function calculate($expression) {
            assert($this->validateExpression($expression), new Exception('Invalid RPN expression.'));
            
            $tokens = array_reverse(explode(' ', $expression));
            return $this->evaluate($tokens);
        }
    }
    
    $calculator = new ReversePolishNotationCalculator();
    
    $tests = array(
        '5 3 +' => 8,
        '5 3 -' => 2,
        '15 3 /' => 5,
        '15 3 x' => 45,
        '5 3 - 8 x' => 16,
        '8 5 3 - x' => 16,
        '1 1 + 2 + 3 1 1 + 7 - 15 / x -' => 5
    );
    
    foreach($tests as $expression=>$expected) {
        $actual = $calculator->calculate($expression);
        assert($actual == $expected, new Exception("Expression '$expression': expected '$expected' but got '$actual' instead."));
    }
    
    echo 'All tests passed!';
    ?>
    
    3 votes
  8. Flashynuff
    Link
    I've been looking for a job lately, so I've been trying to do more programming challenges to keep my skills sharpish. Thanks for posting these, they've been a great help! Anyways, I went for Java...

    I've been looking for a job lately, so I've been trying to do more programming challenges to keep my skills sharpish. Thanks for posting these, they've been a great help!

    Anyways, I went for Java this time. It accepts + - * / as operators, and expects tokens to be separated by spaces.
    It always surprises me at the things you can't do in Java without some complicated setup, like reading in lines from the console or pushing / popping elements to/from an array.

    import java.util.Scanner;
    import java.util.Stack;
    import java.util.EmptyStackException;
    import java.util.Arrays;
    
    public class RPNCalculator {
      public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        System.out.println("Enter RPN String. Valid operators are + - * /");
        String[] rpn = scan.nextLine().trim().split(" ");
        System.out.println("You entered: " + Arrays.toString(rpn));
    
        scan.close();
    
        Stack<Float> operatorStack = new Stack<Float>();
        int count = 0;
    
        for (String token : rpn ) {
          if(token.matches("[0-9\\.]+")) {
            operatorStack.push(new Float(token));
            count++;
          }
          else if (token.matches("[\\+\\-\\*\\/]")) {
            try {
              Float operand_2 = operatorStack.pop();
              Float operand_1 = operatorStack.pop();
              count -= 2;
              if(count < 0) {
                System.out.println("The RPN string is invalid. Please verify you have entered valid Reverse Polish Notation.");
                break;
              }
              count++;
    
              switch (token) {
                case "+": operatorStack.push(operand_1 + operand_2);
                          break;
                case "-": operatorStack.push(operand_1 - operand_2);
                          break;
                case "*": operatorStack.push(operand_1 * operand_2);
                          break;
                case "/": operatorStack.push(operand_1 / operand_2);
                default:  break;
              }
            }
            catch(EmptyStackException e) {
              System.out.println("The RPN string is invalid. Please verify you have entered valid Reverse Polish Notation.");
              System.exit(1);
            }
          }
        }
        try {
          Float result = operatorStack.pop();
          if (count == 1)
            System.out.println(result);
          else
            System.out.println("Please verify that you have entered a valid RPN string.");
        }
        catch(EmptyStackException e) {
          System.out.println("Please verify that you have entered a valid RPN string.");
        }
      }
    }
    
    3 votes
  9. teaearlgraycold
    Link
    import re from typing import List, Union operators = { "+": lambda x, y: x + y, "-": lambda x, y: x - y, "/": lambda x, y: x / y, "*": lambda x, y: x * y } def is_float(token: str) -> bool: try:...
    import re
    from typing import List, Union
    
    
    operators = {
        "+": lambda x, y: x + y,
        "-": lambda x, y: x - y,
        "/": lambda x, y: x / y,
        "*": lambda x, y: x * y
    }
    
    
    def is_float(token: str) -> bool:
        try:
            float(token)
            return True
        except:
            return False
    
    
    def tokenize(expr: str) -> List[str]:
        return re.findall(r"(\d(?:\.\d+)?|[+\-/*])", expr)
    
    
    def cast_tokens(tokens: List[str]) -> List[Union[float, str]]:
        return [
            float(token) if is_float(token) else token
            for token in tokens
        ]
    
    def calculate(expr: str) -> float:
        stack = []
        tokens = cast_tokens(tokenize(expr))
    
        for token in tokens:
            if isinstance(token, float):
                stack.append(token)
            else:
                x = stack.pop()
                y = stack.pop()
                result = operators[token](x, y)
                stack.append(result)
    
        if len(stack) > 1:
            raise ValueError("Invalid expression.")
    
        return stack[0]
    
    
    def main():
        while True:
            expr = input("Enter a RPN expression: ")
            print("= {}".format(calculate(expr)))
    
    
    if __name__ == "__main__":
        main()
    
    2 votes