Polish Notation Solution

  • 0

    Polish notation is something a lot of young programmers and computer scientists may have a little bit of trouble wrapping their heads around. When I first learned about it in my early Discrete Mathematics course, it took me a bit to actually figure out how it worked.

    Here is a straight forward way to do it, with stacks.

    int evalRPN(vector<string>& tokens)
        // do not forget about EDGE and CORNER cases
        if(tokens.empty()) return 0;
        int x, y, n = tokens.size();
        stack<string> s;
        for(const auto& c: tokens)
              if(!((c == "+") || (c == "-") || (c == "*") || (c == "/"))) s.push(c);
              else {
                  y = stoi(s.top());
                  x = stoi(s.top());
                  if(c[0] == '+') x += y;
                  else if(c[0] == '-')  x -= y;
                  else if(c[0] == '*') x -= y;
                  else x /= y;
                 // as a note one should always put in a way to handle dividing by zero.             
               return stoi(s.top());

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.