题目:
解答：
解题思路：
此题主要通过如下两个步骤来完成：
（1）将输入的中缀表达式转为后缀表达式（即逆波兰表达式）；
（2）计算逆波兰表达式；
用到的数据结构主要是栈。
中缀表达式转后缀表达式（逆波兰表达式）
（1）变量及函数说明
getPriority(char ch): 返回运算符的优先级
vector<char> ans: 存储逆波兰表达式
stack<char> op: 暂存未输出的运算符
（2）步骤
i. 如果s[i]为数字，则一直向后寻找到第一个非数字字符，并将之前的数字字符放入ans
ii. 如果s[i]为运算符，则分为以下三种情况：
A. 如果op为空，则直接将运算符s[i]压入栈op；
B. 如果栈op非空，且运算符s[i]的优先级高于栈顶元素的优先级，则直接将元素符s[i]压入栈op；
C. 如果栈op非空，且运算符s[i]的优先级低于或等于栈顶元素的优先级，则弹出栈顶元素，并将其放入ans，直到运算符s[i]的优先级高于栈顶元素的优先级，此时将运算符s[i]压入栈op.
计算后缀表达式（逆波兰表达式）
（1）变量说明：
stack<int> value: 存储操作数以及中间运算结果
（2）步骤：
1. 如果遇到数字，则将其压入栈value;
2. 如果遇到运算符，则从栈value从弹出两个操作数，计算结果，并将结果压入栈value
3. 遍历完逆波兰表达式后，返回value栈顶元素
1 class Solution { 2 public: 3 // get the priority of the operator 4 int getPriority(char ch) 5 { 6 switch(ch) 7 { 8 case ‘+‘: return 1; 9 case ‘-‘: return 1; 10 case ‘*‘: return 2; 11 case ‘/‘: return 2; 12 default: return 0; 13 } 14 } 15 16 // convert infix expression to postfix expression 17 vector<char> toRPN(string s) 18 { 19 vector<char> ans; // store the postfix expression 20 stack<char> op; // operator stack 21 int len = s.length(); 22 for(int i = 0; i < len; ++i) 23 { 24 // jump the space 25 if(s[i] == ‘ ‘) 26 { 27 continue; 28 } 29 30 // if s[i] is a digit, put the value into ans directly 31 if(s[i] >= ‘0‘ && s[i] <= ‘9‘) 32 { 33 while(s[i] >= ‘0‘ && s[i] <= ‘9‘) 34 { 35 ans.push_back(s[i]); 36 ++i; 37 } 38 ans.push_back(‘ ‘); 39 --i; 40 } 41 // if s[i] is an operator 42 if(s[i] == ‘+‘ || s[i] == ‘-‘ || s[i] == ‘*‘ || s[i] == ‘/‘) 43 { 44 // if op is empty, push s[i] directly 45 if(op.empty()) 46 { 47 op.push(s[i]); 48 } 49 // if op is not empty, we should compare the priority 50 else 51 { 52 if(getPriority(s[i]) > getPriority(op.top())) 53 { 54 op.push(s[i]); 55 } 56 else 57 { 58 while(!op.empty() && (getPriority(s[i]) <= getPriority(op.top()))) 59 { 60 ans.push_back(op.top()); 61 ans.push_back(‘ ‘); 62 op.pop(); 63 } 64 op.push(s[i]); 65 } 66 } 67 68 } 69 } 70 while(!op.empty()) 71 { 72 ans.push_back(op.top()); 73 ans.push_back(‘ ‘); 74 op.pop(); 75 } 76 return ans; 77 } 78 79 int calculateRPN(vector<char> str) 80 { 81 int len = str.size(); 82 int value1, value2, ans; 83 stack<int> value; 84 for(int i = 0; i < len; ++i) 85 { 86 if(str[i] >= ‘0‘ && str[i] <= ‘9‘) 87 { 88 int tmp = str[i] - 48; 89 int j = ++i; 90 while(str[j] >= ‘0‘ && str[j] <= ‘9‘) 91 { 92 tmp = tmp * 10 + (str[j] - 48); 93 ++j; 94 } 95 value.push(tmp); 96 i = --j; 97 } 98 if(str[i] == ‘+‘ || str[i] == ‘-‘ || str[i] == ‘*‘ || str[i] == ‘/‘) 99 { 100 value2 = value.top(); 101 value.pop(); 102 value1 = value.top(); 103 value.pop(); 104 if(str[i] == ‘+‘) ans = value1 + value2; 105 else if(str[i] == ‘-‘) ans = value1 - value2; 106 else if(str[i] == ‘*‘) ans = value1 * value2; 107 else ans = value1 / value2; 108 value.push(ans); 109 } 110 } 111 return value.top(); 112 } 113 114 int calculate(string s) 115 { 116 return calculateRPN(toRPN(s)); 117 } 118 };
原文：https://www.cnblogs.com/ocpc/p/12826597.html