evalRPN 逆波兰算术

#include <iostream>
#include <stack>
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
      stack<int> nums;
      for(auto& x: tokens) {
        if(!isdigit(x[0])) {
          int n2 = nums.top(); nums.pop();
          int n1 = nums.top(); nums.pop();
          if(x == "+") nums.push(n1 + n2);
          else if(x == "-") nums.push(n1 - n2);
          else if(x == "*") nums.push(n1 * n2);
          else if(x == "/") nums.push(n1 / n2);
        } else nums.push(stoi(x));
      }
      return nums.top();
    }
    // 转化为逆波兰表达式
    vector<string> toRPN(string& s) {
      unordered_map<string, int> priority;
      priority["*"] = priority["/"] = 2;
      priority["+"] = priority["-"] = 1;
      priority["("] = 0;

      vector<string> ans; stack<string> ops;
      if(!s.size()) return ans;
      s.insert(0, 1, ‘(‘); s.push_back(‘)‘);

      for(int i = 0; i < s.size(); i++) {
        if(isdigit(s[i])) {
          string cur = "";
          while(i < s.size() && isdigit(s[i])) {
            cur += s[i];
            i++;
          }
          i--;
          ans.push_back(cur);
        } else if(s[i] == ‘(‘) ops.push("(");
        else if(s[i] == ‘)‘) {
          while(ops.top() != "(") {
            ans.push_back(ops.top());
            ops.pop();
          }
          ops.pop();
        } else {
          // + - * /
          string cur = string(1, s[i]);
          if(ops.empty() || priority[cur] > priority[ops.top()]) ops.push(cur);
          else {
            while(!ops.empty()) {
              if(priority[cur] <= priority[ops.top()]) {
                ans.push_back(ops.top());
                ops.pop();
              } else break;
            }
            ops.push(cur);
          }
        }
      }
      return ans;
    }
    int solve(string s) {
        // write code here
        vector<string> tokens = toRPN(s);
        return evalRPN(tokens);
    }
};

evalRPN 逆波兰算术

原文：https://www.cnblogs.com/littlepage/p/14457042.html