逆波蘭表達式求值

這是一道經典地使用棧來解決后綴表達式求解的題目。使用棧來求解后綴表達式的流程如下：

借助棧的結構，可以求解出原始表達式是：9 +（-3 - 1）* 3 + 10 / 2 = 2，在遵照規則過程中，還有些細節要注意：

1. ??數字字符串如何轉化為整數格式？尤其是負數。
2. 注意遇到計算符號時，從棧中出棧用于計算的兩個數，對于減法和除法是有序的，被減數/被除數應該是按照原始的入棧順序來確定，也就是先入棧的是被減數/被除數，所以先出棧的是減數/除數。

代碼如下，因為考慮到耗時上的加速，所以直接使用字符數組來表示棧，棧頂通過數組長度這個變量來維護：

class Solution {
public:int getInt(string s){//如果字符串是計算符，返回201int num = 201;if(s.length()==1&&(s[0]=='-'||s[0]=='+'||s[0]=='*'||s[0]=='/')){num = 201;}//字符串是數字，則轉化為int值else{if(s[0]=='-'){//這是一個負數num = 0;for(int i = 1;i<s.length();i++){num = 10 * num + s[i]-'0';}num = -num;}else{//非負數num = 0;for(int i=0;i<s.length();i++){num  = num *10 +s[i]-'0';}}}return num;}int evalRPN(vector<string>& tokens) {int num_stack[10001];int stack_cnt = 0;for(int i= 0;i<tokens.size();i++){if(getInt(tokens[i])==201){//遇到計算符，就兩個數字出棧，計算結果，并把結果放回到棧中int num2 = num_stack[stack_cnt-1];stack_cnt--;int num1 = num_stack[stack_cnt-1];stack_cnt--;int res = 0;if(tokens[i]=="+"){res = num1+num2;}else if(tokens[i]=="-"){res = num1 - num2;}else if(tokens[i]=="*"){res = num1 * num2;}else if(tokens[i]=="/"){res = num1 / num2;}num_stack[stack_cnt++]=res;}else{//遇到數字就入棧num_stack[stack_cnt++]=getInt(tokens[i]);}}return num_stack[stack_cnt-1];}
};