? ? ? ? 本片內容我們將針對于一個力扣中的一道很經典的習題：基本計算器。

? ? ? ? 這道題目十分經典，在很多大廠的面試題中都有出現過

? ? ? ? 因此我們將進一步來學習

? ? ? ? 該題目代碼已經上傳作者的個人gitee：CPP 學習代碼庫: C++代碼庫新庫，舊有C++倉庫滿員了喜歡請支持一下謝謝。

題目：

? ? ? ? 實現的思路：

????????計算器顧名思義就是我們給一個計算表達式讓其把計算結果求解出來。日常生活中我們使用的都是中綴表達式。也就是運算符在中間、運算數在兩邊的表達式，比如1-（3-2）*5。但是中綴表達式涉及到優先級的問題，對于計算器而言沒辦法直接解決這個問題。

? ? ? ? 其中的一種設計思路是可以將中綴表達式轉換為后綴表達式。將操作符放到操作數后面，運算符運算的順序就是運算符出現的順序。

? ? ? ? 后綴表達式/逆波蘭表達式的計算

? ? ? ? 逆波蘭表達式的講解可以參考以下資料：【數據結構】你知道波蘭表達式和逆波蘭表達式嗎？我才知道原來棧在表達式求值中還能這樣使用……-騰訊云開發者社區-騰訊云

? ? ? ? 逆波蘭表達式在力扣上也有習題：150. 逆波蘭表達式求值 - 力扣（LeetCode）

????????

????????

? ? ? ? 思路：

? ? ? ? 后綴表達式因為已經確定好優先級，運算符方式非常簡單，就是遇到運算符的時候取前面兩個運算數進行運算。因為經過中綴表達式后后綴表達式已經確定好了。

? ? ? ? 建立一個棧存儲數據，讀取后綴表達式，遇到運算數入棧，遇到運算符出棧頂兩個數據運算后的結果作為數據入棧參與下一次運算。讀取結束后，棧內的結果就是表達式的值。????????

? ? ? ?因此實際上后綴表達式進行四則運算的結果為：

class Solution {
public:int evalRPN(vector<string>& tokens) {stack<int> st;for(auto& str:tokens){if(str=="+"||str=="-"||str=="*"||str=="/"){//遇到運算符要出棧兩個運算數然后運算后入棧int right=st.top();st.pop();int left=st.top();st.pop();switch(str[0]){case '+':st.push(left+right);break;case '-':st.push(left-right);break;case '*':st.push(left*right);break;case '/':st.push(left/right);break;default:break;}}else{//運算數入棧st.push(stoi(str));}}        return st.top();}
};

????????中綴表達式轉后綴表達式

? ? ? ? 依次讀取計算表達式上的數值，直到遇到運算數直接輸出。

? ? ? ? 建立一個棧存儲運算符，利用棧后進先出的特性遇到后米娜的運算符，出棧里面前面的運算符進行比較，確定優先級。

? ? ? ? 遇到運算符，如果棧為空或者棧不為空且當前運算符比棧頂運算符高的時候，則當前運算符入棧。因為如果棧里存儲的是前一個運算符，當前運算符比前一個高，則說明前一個運算符不能運算、當前運算符也不能運算，因為后面可能有優先級更高的。

? ? ? ? 遇到運算符，如果棧不為空且當前運算符比棧頂運算符低或者相等的時候，說明棧頂的運算符可以運算了，則輸出棧頂運算符，當前運算符繼續走前面遇到運算符的邏輯。

? ? ? ? 如果遇到（），則把（）的計算表達式當成一個子表達式，和上面的思路類似，進行遞歸處理子表達式，處理轉換之后的后綴表達式加在前面表達式的后面即可。

? ? ? ? 計算表達式或（）中子表達式結束值，輸出棧中所有的運算符

? ? ? ? 代碼實現

//比較運算符優先級大小
//方案一：
int operatorpriority(char ch)
{struct opPD{char _op;//運算符int _pd;//優先級};static const opPD opPrecedence[] = { {'+',1},{'-',1},{'*',2},{'/',2}};for (auto& str: opPrecedence){if (str._op == ch){return str._pd;}}assert(false);return -1;}
//方案二：
int operatorprecdence(char ch)
{map<char, int> mp = { {'+',1},{'-',1},{'*',2},{'/',2} };for (auto& str : mp){if (str.first == ch){return str.second;}}assert(false);return -1;
}
//中綴表達式轉后綴表達式
//i是遞歸的下標
//vector<string>存儲結果
void toPRN(const string& s,size_t& i,vector<string>&v)
{stack<char> st;//遍歷中綴表達式while (i<s.size()){//判斷是否為數字if (isdigit(s[i])){//如果是操作數、運算數就直接輸出string num;while (i < s.size()&&isdigit(s[i])){num += s[i];++i;}v.push_back(num);}//開始遞歸else if (s[i]=='('){//子表達式,遞歸處理++i;toPRN(s, i, v);}//結束遞歸else if (s[i] == ')'){//子表達式結束//彈出棧頂剩余運算符while (!st.empty()){v.push_back(string(1,st.top()));st.pop();}++i;return;}else{//如果是運算符//棧為空或者棧運算符優先級高if (st.empty()|| operatorprecdence(s[i])> operatorprecdence(st.top())){st.push(s[i]);++i;}else{//棧不為空且棧頂運算符優先級相等或低char op = st.top();st.pop();//用string 構造v.push_back(string(1,op));}}//表達式結束//彈出棧頂剩余運算符while (!st.empty()){v.push_back(string(1, st.top()));st.pop();}}
}

????????

基本計算器代碼實現

????????

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<map>
#include<string>
#include<stack>
#include<vector>
#include<assert.h>
using namespace std;
class Solution 
{
public://map<char, int> _operatorPrecedence = { { '+', 1 }, { '-', 1 }, { '*', 2 }, { '/', 2 } };int operatorPrecedence(char ch){struct opPD{char _op;int _pd;};static opPD arr[] = { {'+', 1},{'-', 1},{'*', 2},{'/', 2} };for (auto& e : arr){if (e._op == ch){return e._pd;}}assert(false);return -1;}void toRPN(const string& s, size_t& i, vector<string>& v){stack<char> st;while (i < s.size()){if (isdigit(s[i])){// 運算數輸出string num;while (i < s.size() && isdigit(s[i])){num += s[i];++i;}v.push_back(num);}else{if (s[i] == '('){// 遞歸?式處理括號中的?表達式++i;toRPN(s, i, v);}else if (s[i] == ')'){++i;// 棧中的運算符全部輸出while (!st.empty()){v.push_back(string(1, st.top()));st.pop();}//結束遞歸return;}else{//運算符// 1、如果棧為空或者棧不為空且當前運算符?棧頂運算符優先級?，則當 前運算符?棧// 2、如果棧不為為空且?棧頂運算符優先級低或相等，說明棧頂的運算符可以運算了，// 輸出棧頂運算符，當前運算符繼續?前?遇到運算符的邏輯if (st.empty() || operatorPrecedence(s[i]) >operatorPrecedence(st.top())){st.push(s[i]);++i;}else{v.push_back(string(1, st.top()));st.pop();}}}}//棧中的運算符全部輸出while (!st.empty()){v.push_back(string(1, st.top()));st.pop();}}int evalRPN(const vector<string>& tokens) {stack<int> s;for (size_t i = 0; i < tokens.size(); ++i){const string& str = tokens[i];// str為數字if (!("+" == str || "-" == str || "*" == str || "/" == str)){s.push(stoi(str));}else{// str為操作符int right = s.top();s.pop();int left = s.top();s.pop();switch (str[0]){case '+':s.push(left + right);break;case '-':s.push(left - right);break;case '*':s.push(left * right);break;case '/':s.push(left / right);break;}}}return s.top();}int calculate(string s){// 1、去除所有空格，否則下?的?些邏輯沒辦法處理std::string news;news.reserve(s.size());for (auto ch : s){if (ch != ' ')news += ch;}s.swap(news);news.clear();// 2、將所有的負數 - x轉換為0 - xfor (size_t i = 0; i < s.size(); ++i){if (s[i] == '-' && (i == 0 || (!isdigit(s[i - 1]) && s[i - 1] !=')')))news += "0-";elsenews += s[i];}// 中綴表達式轉成后綴表達式size_t i = 0;vector<string> v;toRPN(news, i, v);// 后綴表達式進?運算return evalRPN(v);}
};

（科普）前綴/中綴/后綴表達式

核心概念：操作符的位置

這些表達式類型的核心區別在于操作符相對于操作數的位置。

1. 操作數 (Operand):?表示參與運算的值（如數字、變量）。例如?a,?5,?x。

2. 操作符 (Operator):?表示要執行的運算（如?+,?-,?*,?/）。例如?+,?*。

---

1. 中綴表達式 (Infix Notation)

• 定義：?這是我們日常生活中最熟悉、最常用的數學表達式書寫方式。操作符位于兩個操作數之間。

• 特點:

  • 符合人類的閱讀和書寫習慣。

  • 需要括號和操作符優先級（如?*?和?/?比?+?和?-?優先）來確定運算順序。這是它最大的復雜性來源。

  • 對計算機不友好，因為計算機需要解析括號和優先級才能確定計算順序。

• 示例:

  • A + B

  • (A + B) * C

  • A + B * C - D / E

  • ( (A + B) * (C - D) ) / E

---

2. 后綴表達式 (Postfix Notation) / 逆波蘭表達式 (Reverse Polish Notation - RPN)

• 定義：?操作符位于其對應的操作數之后。

• 特點:

  • 也稱為逆波蘭表達式 (RPN)。這是波蘭數學家的發明，后綴是“逆”著前綴的順序來的。

  • 完全不需要括號！表達式的結構本身就隱含了唯一的運算順序。

  • 對計算機極其友好。使用一個簡單的棧 (Stack)?數據結構就能高效地計算出結果，無需考慮優先級和括號。

  • 計算過程是從左到右線性掃描。

• 計算規則 (使用棧):

  1. 從左到右掃描表達式。

  2. 遇到操作數：將其壓入棧中。

  3. 遇到操作符：

     • 從棧頂彈出所需數量的操作數（二元操作符彈出兩個，一元操作符彈出一個）。

     • 用該操作符對彈出的操作數進行運算。

     • 將運算結果壓回棧中。

  4. 重復步驟 1-3，直到表達式結束。

  5. 棧中最后剩下的唯一元素就是整個表達式的計算結果。

• 示例 (與中綴對應):

  • 中綴?A + B?-> 后綴?A B +

  • 中綴?(A + B) * C?-> 后綴?A B + C *

  • 中綴?A + B * C?-> 后綴?A B C * +?(注意：*?優先級高，先結合?B?和?C)

  • 中綴?A * B + C?-> 后綴?A B * C +

  • 中綴?(A + B) * (C - D)?-> 后綴?A B + C D - *

  • 中綴?( (A + B) * (C - D) ) / E?-> 后綴?A B + C D - * E /

• 為什么叫“逆波蘭”？?它是“波蘭表達式”（前綴表達式）的“逆序”版本（操作符在操作數后面 vs. 操作符在操作數前面）。

---

3. 前綴表達式 (Prefix Notation) / 波蘭表達式 (Polish Notation - PN)

• 定義：?操作符位于其對應的操作數之前。

• 特點:

  • 也稱為波蘭表達式 (PN)。

  • 和 RPN 一樣，完全不需要括號！表達式的結構隱含了唯一的運算順序。

  • 同樣對計算機友好，也可以用棧高效計算（掃描方向不同）。

  • 計算過程需要從右到左掃描。

• 計算規則 (使用棧):

  1. 從右到左掃描表達式。

  2. 遇到操作數：將其壓入棧中。

  3. 遇到操作符：

     • 從棧頂彈出所需數量的操作數（二元操作符彈出兩個，一元操作符彈出一個）。

     • 用該操作符對彈出的操作數進行運算。

     • 將運算結果壓回棧中。

  4. 重復步驟 1-3，直到表達式開始。

  5. 棧中最后剩下的唯一元素就是整個表達式的計算結果。

• 示例 (與中綴對應):

  • 中綴?A + B?-> 前綴?+ A B

  • 中綴?(A + B) * C?-> 前綴?* + A B C

  • 中綴?A + B * C?-> 前綴?+ A * B C?(注意：*?優先級高，先結合?B?和?C)

  • 中綴?A * B + C?-> 前綴?+ * A B C

  • 中綴?(A + B) * (C - D)?-> 前綴?* + A B - C D

  • 中綴?( (A + B) * (C - D) ) / E?-> 前綴?/ * + A B - C D E

• 為什么叫“波蘭”？?由波蘭數學家揚·武卡謝維奇（Jan ?ukasiewicz）在 1920 年代發明而得名。

---

總結對比表

特性	中綴表達式 (Infix)	后綴表達式 (Postfix) / 逆波蘭 (RPN)	前綴表達式 (Prefix) / 波蘭 (PN)
操作符位置	在操作數之間	在操作數之后	在操作數之前
括號需求	必需?(消除歧義)	不需要	不需要
優先級需求	必需?(確定運算順序)	不需要?(順序隱含)	不需要?(順序隱含)
人類可讀性	最好?(最自然)	較差	較差
計算機友好度	最差?(解析復雜)	很好?(棧，左->右掃描)	很好?(棧，右->左掃描)
計算掃描方向	無固定方向 (需解析)	左 -> 右	右 -> 左
別名	-	逆波蘭表達式 (RPN)	波蘭表達式 (PN)
示例	(A + B) * C - D / E	A B + C * D E / -	- * + A B C / D E
核心優勢	符合直覺	無括號，易計算	無括號，易計算
核心劣勢	需括號和優先級，難解析	對人類不直觀	對人類不直觀

????????
?

? ? ? ? 本期內容就到這里了，喜歡請點個贊謝謝