本片内容我们将针对于一个力扣中的一道很经典的习题：基本计算器。
这道题目十分经典，在很多大厂的面试题中都有出现过
因此我们将进一步来学习
该题目代码已经上传作者的个人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 - x
for (size_t i = 0; i < s.size(); ++i)
{
if (s[i] == '-' && (i == 0 || (!isdigit(s[i - 1]) && s[i - 1] !=
')')))
news += "0-";
else
news += s[i];
}
// 中缀表达式转成后缀表达式
size_t i = 0;
vector<string> v;
toRPN(news, i, v);
// 后缀表达式进⾏运算
return evalRPN(v);
}
};
（科普）前缀/中缀/后缀表达式
核心概念：操作符的位置
这些表达式类型的核心区别在于操作符相对于操作数的位置。
操作数 (Operand): 表示参与运算的值（如数字、变量）。例如
a,5,x。操作符 (Operator): 表示要执行的运算（如
+,-,*,/）。例如+,*。
1. 中缀表达式 (Infix Notation)
定义： 这是我们日常生活中最熟悉、最常用的数学表达式书写方式。操作符位于两个操作数之间。
特点:
符合人类的阅读和书写习惯。
需要括号和操作符优先级（如
*和/比+和-优先）来确定运算顺序。这是它最大的复杂性来源。对计算机不友好，因为计算机需要解析括号和优先级才能确定计算顺序。
示例:
A + B(A + B) * CA + B * C - D / E( (A + B) * (C - D) ) / E
2. 后缀表达式 (Postfix Notation) / 逆波兰表达式 (Reverse Polish Notation - RPN)
定义： 操作符位于其对应的操作数之后。
特点:
也称为逆波兰表达式 (RPN)。这是波兰数学家的发明，后缀是“逆”着前缀的顺序来的。
完全不需要括号！表达式的结构本身就隐含了唯一的运算顺序。
对计算机极其友好。使用一个简单的栈 (Stack) 数据结构就能高效地计算出结果，无需考虑优先级和括号。
计算过程是从左到右线性扫描。
计算规则 (使用栈):
从左到右扫描表达式。
遇到操作数：将其压入栈中。
遇到操作符：
从栈顶弹出所需数量的操作数（二元操作符弹出两个，一元操作符弹出一个）。
用该操作符对弹出的操作数进行运算。
将运算结果压回栈中。
重复步骤 1-3，直到表达式结束。
栈中最后剩下的唯一元素就是整个表达式的计算结果。
示例 (与中缀对应):
中缀
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-3，直到表达式开始。
栈中最后剩下的唯一元素就是整个表达式的计算结果。
示例 (与中缀对应):
中缀
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 |
| 核心优势 | 符合直觉 | 无括号，易计算 | 无括号，易计算 |
| 核心劣势 | 需括号和优先级，难解析 | 对人类不直观 | 对人类不直观 |
本期内容就到这里了，喜欢请点个赞谢谢