Polish Notation Solution


  • 0
    A

    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());
                  s.pop();
                  x = stoi(s.top());
                  s.pop();
                  if(c[0] == '+') x += y;
                  else if(c[0] == '-')  x -= y;
                  else if(c[0] == '*') x -= y;
                  else x /= y;
    
                  s.push(to_string(x));
    
                 // 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.