C++实现对数学基本运算表达式的解析
前段时间在LeetCode上刷题，遇到了很多涉及对字符串进⾏解析的题⽬。可能是出于这个原因，最近迷恋上了字符串的解析问题。数学基本运算表达式的解析就涉及这类问题。所谓数学基本运算表达式的解析就是指给定⼀个表达式字符串，如1 + 1，3 * 9，对这个字符串进⾏解析，从⽽得到这个表达式的运算结果。（数学基本运算表达式也就是只⽤加减乘除进⾏计算的数学表达式）
其实站在我的⾓度来看，我觉得对数学基本运算表达式的解析还是有⼀定难度的。因为如果⼀开始没有正确的思路，我们是很难到这个问题的着⼿点的，毕竟解析数学基本运算表达式需要考虑到的问题是有点多的，以下，我把其中主要的问题列举出来：
1. 乘除法优先计算
2. 括号⾥的内容优先计算
3. 表达式中的数字前可能存在正负号
这些问题如果得不到恰当的处理，就会使解析过程失败。
在实现解析数学基本运算表达式之前，我们⾸先得弄清楚哪些表达式是合法的，哪些表达式是不合法的。以下我将列举C/C++等语⾔中，⼀些合法与不合法的表达式：
/* 合法 */
7 + 22 + 7 * 27
6 + -13 * 23 / -30 / 35
24 - +34
10 + (3 * 9) / 8
/* 不合法 */
abc + 123// abc不是数字
1 +
2 *  // *后缺少数字
6 + + 12// 不能连⽤加号
8 - - 17// 不能连⽤减号
32 + () - 4// 括号中没有内容
(0 + 5)) * 7// 右括号多了⼀个
((11 + 9) / 2// 左括号多了⼀个
不排除有⼀些编程语⾔⽀持上述所说的部分或者全部不合法表达式，但这⾥我们先使⽤C/C++标准。
原理讲解
由于实现的过程很“绕圈⼦”，所以我就先把我的实现思路和原理告诉⼤家，供⼤家参考。后⽂会提供相关源代码下载。
（可能⽹上有⼤佬提供了更好、更⾼效的解析数学表达式⽅法，不过我认为我的处理⽅式是⾮常直⽩易懂的⼀种。）
⾸先，我们来回忆⼀下我们做数学计算时的情形：
第⼀步 如果数学运算表达式存在括号的话，我们会率先到括号⾥的内容，并将括号⾥的内容当作⼀个新的数学表达式进⾏优先运算。将这个新的数学表达式进⾏运算后，⽤得到的结果将括号及括号间
的内容替换掉。当我们把所有括号⾥的内容都⽤相应的结果替换掉后，就能得到原先数学表达式消去括号后的简化式⼦，然后我们再对这个式⼦进⾏处理。例如原有的数学式7 * (5 + 3)，进⾏消去括号的处理后，就得到了7 * 8，接下来我们再对这个式⼦进⾏解析和计算，就能得到答案。
第⼆步 消去括号的数学基本运算表达式就只剩加减乘除符号以及数字、⼩数点（如果有⼩数的话）了。由于乘法和除法要优先运算，如果式⼦中有这两种运算的话，我们就要率先在式⼦中进⾏乘法运算和除法运算。运算的过程中，我们采⽤的做法同样是把运算得到的结果替换掉原来的运算式⼦。如下计算过程⽰例可能会让你重拾这⼀过程：
7 + 18 * 5 / 9
|
v
7 + 90 / 9
|
v
7 + 10
第三步 进⾏完前两步的处理，剩下的式⼦就只有加减符号以及数字、⼩数点（如果有⼩数的话）了。⽤和第⼆步中类似的做法进⾏计算，最后，式⼦就化成了数字，这个数字就是我们的答案。以第⼆步⽰例中最后得到的式⼦为例，7 + 10运算得到17，17就是最后的答案。
现在，我们回忆完了平⽇⾥我们进⾏数学计算的步骤，其实这就是⼀个对表达式逐渐化简的过程。接下来我们就要从这些步骤中构思我们的解析算法。
在第⼀步中，我们提到了对括号⾥的内容进⾏优先计算。但是我们可能会遇到括号套括号的问题。但是正如第⼀步中所说，我们可以把括号⾥的式⼦当作新的⼀个式⼦来处理，对于新的式⼦⼜可以采⽤第⼀步到第三步的⽅式依次进⾏处理得到结果，其中的第⼀步⼜可以对新式⼦中的⼦括号进⾏处理。这样⼀来就形成了⼀种递归关系。所以，我们只⽤实现如下⼏个接⼝，就能完成对数学基本运算式的解析：
接⼝A：处理运算式的统⼀接⼝
接⼝B：处理括号的接⼝
接⼝C：处理运算符的接⼝，⼀次可处理两种运算符（因为四则运算符可以分成 乘除⼀组，加减⼀组）
接⼝D：基本运算接⼝，即针对两个数字之间四则运算的接⼝（因为任意的数学表达式都可以通过两两计算进⾏化简求值）
接⼝E：处理字符串的⼀个接⼝集合，提供了剔除字符串左右空⽩或者所有空⽩的接⼝、float与std::string相互转化的接⼝（为了⽅便⼩数计算，使⽤float类型）
第⼀步⽤接⼝B来完成，第⼆、三步⽤接⼝C来完成。接⼝C中使⽤接⼝D来进⾏结果运算，即接⼝C进⾏的操作是到运算符并获取运算符两边的数字，然后交给接⼝D对这两个数字按照到的运算符进⾏计算，再将得到的计算结果替换掉式⼦中相应的部分。⽽接⼝E为前⼏个接⼝提供辅助功能。
接⼝A是调⽤其他接⼝的⼀个⼊⼝。接⼝A~D的伪代码如下：
/**
* 接⼝A
* @param exp 需要解析的表达式
*/
float getValue(const string& exp)
{
// 剔除表达式字符串的左右空⽩
string __exp = 接⼝E(exp);
// 处理括号
handleBrackets(__exp);
// 处理乘法除法运算
handleOperator(__exp, pair<string, string>('*', '/'));
// 处理加法减法运算
handleOperator(__exp, pair<string, string>('+', '-'));
// 将`std::string`转化为`float`
float res = 接⼝E(__exp);
// 返回结果
return res;
}
/**
* 接⼝B
* @param exp 需要解析的表达式
*/
void handleBrackets(string& exp)
{
for遍历`exp` {
if遇到括号 {
string content = 获取括号内容;
// 将括号⾥的内容作为新的表达式处理
源代码电影讲解int val = getValue(content);
// 将`float`转化为`std::string`
string valStr = 接⼝E(val);
将`exp`括号部分替换为valStr;
更新`exp`长度和遍历的下标位置;
}
}
}
/
**
* 接⼝C
* @param exp 需要解析的表达式
* @param operators 需要处理的运算符号（乘除⼀组，加减⼀组）
*/
void handleOperator(string& exp, pair<string, string> operators)
{
for遍历`exp` {
if遇到operators中的运算符 {
string strVal1 = 获取进⾏计算的数字1（运算符左侧数字）;
string strVal2 = 获取进⾏计算的数字2（运算符右侧数字）;
/
/ 获取计算结果
float v = basicCalc(strVal1, 运算符, strVal2);
// 将`float`转化为`std::string`
string valStr = 接⼝E(v);
将`exp`括号部分替换为valStr;
更新`exp`长度和遍历的下标位置;
}
}
}
/**
* 接⼝D
* @param s1 ⽤于计算的数字1
* @param _operator 运算符
* @param s2 ⽤于计算的数字2
*/
void basicCalc(const string& s1, const string& _operator, const string& s2)
{
// 将`std::string`转化为`float`
float n1 = 接⼝E(s1);
float n2 = 接⼝E(s2);
根据运算符_operator进⾏n1 n2之间的计算;
}
（⾄于接⼝E，由于是⼀个提供辅助功能的接⼝集，所以上⾯的伪代码中没有给出。具体实现⽅法请参考后⽂给出的源代码）
源代码下载
上⾯的伪代码还只是⼀个⾻架，没有⾎⾁，还不能解决⼀些实际的问题（⽐如前⽂提到的如何处理括号，如何解决数字前的正负号等问题）。⼤家可以参考我给出的完整实现代码：
当然，各位读者也可以根据我前⾯的原理讲解⾃⾏实现算法。
欢迎⼤家提出疑问以及探讨相关话题～

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。