之前和同学讨论如何写中缀表达式的Parser，他的实现是通过表达式树实现的（当然 这是最常用的方法）。我就在想是否可以不构件树，而是通过其他方式在O(n)的时间内完成计算。我的想法是通过两个栈实现，一个处理数字，一个用来处理运算符。运算符和数字除特殊情况下 都应当交替出现，因此只需要一次压入数和运算符，并且确保压入的运算符的优先级大于栈顶的优先级即可保证运算顺序。理论存在，通过C++实现了一下程序。
代码链节：Talentjoe/BasicCalculator: C++ basic calculator parser
由于有括号的加入，并且支持 -/+ 用来修饰一个数，前置判断内容比较复杂。
主要逻辑是通过一个交替状态实现的。通过状态机指示当前应当读取
int state = 0;
///.....
while (formula[pt]) {
currentOp = GetOperator(pt);
///.....
if (state == 0) {
number.push(GetNumber(pt) * (numberState == 0 ? 1 : numberState));
state = 1;
}else if (state == 1) {
while (!Op.empty() && Op.top() >= currentOp && top() != BracketLeft) CalFirst();
Op.push(currentOp);
numberState = 0;
state = 0;
}
}若state 为 0，代表该阶段需要读取数字，因此调用函数.GetNumber，并将其push到数字栈中等待计算。若数字前面跟着 +/-, 会在之前的步骤中将numberState修饰成 1 或 -1，而没有修饰的时候 默认为0 同样乘以1 以此处理正负号的问题。当全部读取完后 将state改为1，表示接下来应当读取运算符
若state 为 1，代表该阶段读取符号。该符号在进入判断前已经读取完成，为enum类型，enum本身将运算符优先级包含在内，通过比较运算符栈的顶部符号判断压入的优先级是否高于栈顶，若不大于，则应当将进行一次运算，保证顺序准确。若栈为空 或者是左括号，那么代表已经无剩余运算 也可以跳出循环。跳出循环后将当前运算符压入栈中，设置numberState 和 state为0。 该次读取结束。
要注意的是，GetNumber, GetOperator 为引用传入，因此会在读取的过程中改变pt的值，不需要额外更新
//CalParser.h
static char CharToNum(char a) {return a-'0';}
//CalParser.cpp
double CalParser::GetNumber(int &pt) {
pt--;
double currentNum = 0;
double currentBase = 1;
while (isdigit(formula[++pt]))
currentNum = 10 * currentNum + CharToNum(formula[pt]);
if (formula[pt] == '.')
while (isdigit(formula[++pt]))
currentBase *= 0.1, currentNum += CharToNum(formula[pt]) * currentBase;
return currentNum;
}以上为GetNumber的实现，为了支持小数 在此处加入 .的判断。并无特殊。
//CalParser.h
enum Operators {
Addition,
Subtraction,
Multiplication,
Division,
Exponentiation,
BracketLeft,
BracketRight,
Error,
};
//CalParser.cpp
CalParser::Operators CalParser::GetOperator(int &pt) {
switch (formula[pt++]) {
case '+': return Addition;
case '-': return Subtraction;
case '*': return Multiplication;
case '/': return Division;
// case '%': return Modulus;
case '^': return Exponentiation;
case '(': return BracketLeft;
case ')': return BracketRight;
default: pt--;
return Error;
}
}以上为GetOperator的实现，目前只支持单个字符的运算符。需要注意的是，如果没有匹配返回Error并且pt并未移动。因此可以在任意轮次前进行判断，不需要担心指针的问题。
//CalParser.h
std::unordered_map<Operators,std::function<double(double,double)>> opMapping{
{Addition, std::plus<double>() },
{Subtraction,std::minus<double>()},
{Multiplication,std::multiplies<double>()},
{Division,std::divides<double>()},
{Exponentiation, [](double a, double b)->double {return exp(log(a)*b) ;} },
};
//CalParser.cpp
void CalParser::CalFirst() {
double b = number.top();
number.pop();
double a = number.top();
number.pop();
Operators op = Op.top();
Op.pop();
number.push(opMapping[op](a, b));
}
以上为计算逻辑，将number栈中的两个元素弹出，并且将运算符栈中的第一个元素弹出，并且进行运算，将运算结果压入栈中。opMapping 为enum类型到函数，这为可拓展性提供了基础。用于可以自行定义运算符和操作逻辑。
void CalParser::CalTillPrevLeftBracket() {
while (!(Op.empty()) && Op.top() != BracketLeft) {
CalFirst();
}
if (Op.empty())
return;
Op.pop();
}
double CalParser::Calculate() {
if (caled) return number.top();
int pt = 0;
int state = 0;
int numberState = 0;
Operators currentOp;
while (formula[pt]) {
ToFirstNoneBlank(pt);
if (!formula[pt])
break;
currentOp = GetOperator(pt);
if (currentOp == BracketLeft) Op.push(currentOp);
else if (currentOp == BracketRight) CalTillPrevLeftBracket();
else if (state == 0 && currentOp != Error) {
if (currentOp == Addition && numberState == 0) numberState = 1;
else if (currentOp == Subtraction && numberState == 0) numberState = -1;
else throw 1;
} else if (state == 0) {
number.push(GetNumber(pt) * (numberState == 0 ? 1 : numberState));
state = 1;
} else if (state == 1) {
while (!Op.empty() && Op.top() >= currentOp && Op.top() != BracketLeft) CalFirst();
Op.push(currentOp);
numberState = 0;
state = 0;
}
}
while (!Op.empty()) {
CalTillPrevLeftBracket();
}
Caled = true;
return number.top();
}其他为一些特殊的判断，如左括号 右括号，应当单独处理。同样处理 +/- 修饰数的逻辑，以及错误报错。此处没有对括号的检查，因为目前只有一种括号 且并不会影响操作逻辑。因此默认自动补全。
经过测试，以上代码可以成功运行并且在O(N)的时间复杂度内完成目标内容。完整代码和测试请访问github链节。