Evaluate Reverse Polish Notation

描述

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Some examples:

  1.   ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  2.   ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

分析

逆波兰表达式是典型的递归结构，所以可以用递归来求解，也可以用栈来求解。

递归版

  1. // Evaluate Reverse Polish Notation
  2. // 递归，时间复杂度O(n)，空间复杂度O(logn)
  3. class Solution {
  4. public:
  5.     int evalRPN(vector &tokens) {
  6.         if (tokens.empty()) return 0;
  7.         int x, y;
  8.         auto token = tokens.back();  tokens.pop_back();
  9.         if (is_operator(token))  {
  10.             y = evalRPN(tokens);
  11.             x = evalRPN(tokens);
  12.             switch(token[0]) {
  13.                 case '+' : x += y; break;
  14.                 case '-' : x -= y; break;
  15.                 case '*' : x *= y; break;
  16.                 default:   x /= y;
  17.             }
  18.         } else  {
  19.             size_t i;
  20.             x = stoi(token, &i);
  21.         }
  22.         return x;
  23.     }
  24. private:
  25.     bool is_operator(const string &op) {
  26.         return op.size() == 1 && string("+-*/").find(op) != string::npos;
  27.     }
  28. };

迭代版

  1. // Max Points on a Line
  2. // 迭代，时间复杂度O(n)，空间复杂度O(logn)
  3. class Solution {
  4. public:
  5.     int evalRPN(vector<string> &tokens) {
  6.         stack<string> s;
  7.         for (auto token : tokens) {
  8.             if (!is_operator(token)) {
  9.                 s.push(token);
  10.             } else {
  11.                 int y = stoi(s.top());
  12.                 s.pop();
  13.                 int x = stoi(s.top());
  14.                 s.pop();
  15.                 switch(token[0]) {
  16.                     case '+' : x += y; break;
  17.                     case '-' : x -= y; break;
  18.                     case '*' : x *= y; break;
  19.                     default:   x /= y;
  20.                 }
  21.                 s.push(to_string(x));
  22.             }
  23.         }
  24.         return stoi(s.top());
  25.     }
  26. private:
  27.     bool is_operator(const string &op) {
  28.         return op.size() == 1 && string("+-*/").find(op) != string::npos;
  29.     }
  30. };

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/stack-and-queue/stack/evaluate-reverse-polish-notation.html