本文最后更新于 130 天前，其中的信息可能已经有所发展或是发生改变。
突然发现写的这玩意，可能和单片机写的小计算器有关系，试了试好像还真的行得通，顺便写一下笔记
概念
相比于解析复杂的中缀表达式（中缀的实现需要双栈/递归），RPN更加符合计算机直觉，只需一个栈即可计算。利用 Shunting-yard 算法，将 RPN 解析为 中缀，对用户更加友好
逆波兰表达式（RPN）：即后缀表达式。不需要括号，就能明确运算顺序的表达式的表示法。他的特点是：
- 运算符在两个数的后面
- 完全没有括号
- 运算顺序完全由运算符和数的 位置 决定
我们平时使用的是中缀表达式：(1 + 2) * 3。而 RPN 是： 1 2 + 3 *
算法实现
- 先创建一个空栈，用于存储。
- 然后，遍历所有标记，拿到 操作数 运算符
- 遇到数字，直接压入栈中
- 遇到运算符了，从 栈顶 弹出 操作数 ，再压回栈中。然后完成了基本的RPN计算！
当结果的栈长度不是1！那就是你太杂鱼把表达式敲错啦，回去再练练吧ww
private static evaluateRPN(tokens: (number | string)[]): number {
const stack: number[] = [];
for (const token of tokens) {
if (typeof token === "number") {
stack.push(token);
} else if (this.isOperator(token)) {
const b = stack.pop()!;
const a = stack.pop()!;
stack.push(this.evaluateOperator(token, a, b));
}
}
if (stack.length !== 1) {
throw new TypeError("居然打出了非法表达式，真是个杂鱼♡");
}
return stack[0]; // 大功告成！赶紧把结果拿起走人吧ww
}嗯嗯，你已经实现了老式的HP 计算器了！但是用户可不会RPN计算，你还需要一个中缀表达式转 RPN 的办法，我们需要写一个 parseExpression
因为我在写公式解析器，所以这里实际会遇到3种可能：中文变量，运算符，数字常量
运算符：栈中运算符弹出到输出队列，把这个运算符压入栈
数字：类型转换（String -> Number），放在输出队列。中文变量加给是否定义检查就好了
将所有东西全部弹到输出队列，就大功告成啦！
private static parseExpression(tokens: string[], context: Record<string, number>): number {
const output: (number | string)[] = [];
const operators: string[] = [];
while (tokens.length > 0) {
const token = tokens[0];
if (this.isOperator(token)) {
while (
operators.length > 0
) {
output.push(operators.pop()!);
}
operators.push(token);
tokens.shift();
} else if (!Number.isNaN(Number(token))) {
output.push(this.parseNumber(token));
tokens.shift();
} else {
if (!(token in context)) {
throw new TypeError(`欸~ 变量“ ${token} ”没定义呢~ 连自己几斤几两都不清楚吗~杂鱼♡杂鱼♡`);
}
output.push(context[token]);
tokens.shift();
}
}
while (operators.length > 0) {
output.push(operators.pop()!);
}
return this.evaluateRPN(output);
}结束了？
还没完！比如后端发来了这种式子： =3 + 4 * 5
按照上面的方法，这将被解释：3 4 + 5 *，再翻译回来，却变成了 (3 + 4) * 5
没错！优先级！虽然纯 RPN 是不需要考虑优先级的，但是我们这里使用了 Shunting-yard 算法解析中缀表达式。我们对 + – 的优先级定为 1，* / 定义为 2，幂运算定义为3 …
然后在弹出栈时，加入判断比较优先级，来跳转输出顺序
while (
operators.length > 0 &&
this.getOperatorPrecedence(operators[operators.length - 1]) >=
this.getOperatorPrecedence(token)
) {
output.push(operators.pop()!); // 弹出高优先级运算符
}
operators.push(token); // 当前运算符入栈这总该结束了吧…
吗？