学会这个表达式，写一个计算器绝对不是问题
本文已在本人微信公众号“码农小阿飞”上发布，打开微信搜索“码农小阿飞”，或者扫描文章结尾的二维码，进入公众号并关注，就可以在第一时间收到我的推文！
前言
前段时间，在逛论坛的时候，看到一个比较有趣的提问：怎么用代码实现一个程序，可以根据用户动态输入的传统算术表达式，去解析并计算这个表达式，最后，给用户返回一个计算结果？当然了，这个算术表达式比较简单，运算操作符只有+-*/()。
例如：用户输入的字符串表达式为5+2*(1+3*(5-1*2))，程序运行结束给用户返回一个计算结果25。那是怎么计算得出这么一个结果的呢？
在这里插入图片描述
“先乘除后加减，有小括号要先计算小括号里的”，幼儿园小朋友可能都知道的逻辑。可是，对计算机来说，只能通过循环和判断等方式来解决问题，怎么用代码来让计算机来根据这个规则去运算呢？
传统思想解法
因为算术表达式的计算是有先后顺序关系，必须先找到表达式中优先级高的运算操作，先计算得出结果，再考虑优先级较低的运算操作，这就涉及到一个寻找匹配的过程，因此自然而然能够想到的就是用正则表达式。
在正则表达式中，用\\([^\\(\\)]*\\)匹配一对没有嵌套的单层括号对，这应该好理解，一对小括号，中间有一串表达式，但是不再嵌套其他小括号。用\\-?\\d+(\\*|\\/)\\-?\\d+匹配乘除运算，用\\-?\\d+(\\+|\\-)\\-?\\d+匹配加减运算。这也好理解，通过+-*/连接的两个数值串，当然，数值可能是负数所以数值的模式串为\\-?\\d+。
最后，只要依次判断这三个正则表达式在当前表达式中是否存在，如果存在，则把匹配的内容取出来做相应的计算操作，并将结果替换原来匹配出来的子串。
举个简单的例子，但凡能被正则表达式\\-?\\d+\\*\\-?\\d+匹配的字符串一定满足格式a*b（a和b都是数值，当然可能是负的），我们只需要以*为分隔符，将子串a和b分隔提取出来，再将子串a和b都转换成int整形进行相应的计算。
if (expression.matches("\\-?\\d+\\*\\-?\\d+")) {
String[] split = expression.split("\\*");
int value1 = Integer.parseInt(split[0]);
int value2 = Integer.parseInt(split[1]);
return value1 * value2;
}
最后再用这个计算结果替换原表达式中的a*b，除法、加法、减法也是这么处理，一步一步以此类推，先匹配再运算，直到表达式再也匹配不到乘除运算和加减运算，就可以输出结果了。
这是我用正则表达式实现的程序，根据输入打印的结果：
在这里插入图片描述
在这里插入图片描述
可以看出来，和我们常规计算算术表达式时的思路一样。
当然，实际代码操作中还有不少细节需要处理，因为篇幅有限，也不是本篇推崇的实现方案，这里提出一种思路，就不在此处做代码展示，对正则表达式实现感兴趣或者想要去了解的朋友可以私信我，一起讨论。
虽然，看起来轻松写意，寥寥几语就把实现方案描绘出来，但用正则表达式匹配字符串总体上还是比较繁琐，效率也比较低，很容易在写匹配模式串的时候，因为考虑不到的情况，导致整个表达式无法解开，而且在拓展更多操作符的时候，也不是太方便。那到底会不会存在更简洁优雅的方式去实现呢？答案是肯定的，那就是今天我要推荐给大伙儿的后缀表达式，一个为计算机执行算术运算而生的表达式。
后缀表达式
后缀大伙儿应该都知道，在英语中可以根据单词的后缀区分词性，在计算机中可以根据文件名的后缀区分文件类型，可是，后缀表达式又是什么呢？它们之间又有着什么样的联系呢？
先来看一个表达式：1 2 3 + 4 * + 5 -。你没看错，我也没有写错，这的的确确是一个表达式，这是就是算术表达式1+((2+3)*4)-5对应的后缀表达式，因为表达式中操作运算符都位于需要进行运算操作的数值的后边（右侧），因而得名后缀表达式。
后缀表达式有一个运算规则：从左往右依次遍历后缀表达式，如果遍历到的元素是数值的话，将数值入栈到一个数值栈中。如果遍历到的元素是运算符的话，取出数值栈栈顶的前两个数值，以"次顶元素 运算符 栈顶元素"的位置关系，做相应的算术运算，并把运算的结果入栈到数值栈中，直到遍历到后缀表达式的末端，再将栈顶的元素取出，便是运算的结果。我们先根据规则，运行上述后缀表达式，运行过程步骤如下图所示：
在这里插入图片描述
/***
* 解析计算给定的后缀表达式
*
* @param rpnExpression 后缀表达式
* */
public int compute(String[] rpnExpression) {
Objects.requireNonNull(rpnExpression, "后缀表达式为空");
Stack<Integer> stack = new Stack<>();
int value1, value2;
for (String string : rpnExpression) {
switch (string) {
case "+": {
if (2 > stack.size()) {
throw new RuntimeException("解析异常");
}
value2 = stack.pop();
value1 = stack.pop();
stack.push(value1 + value2);
break;
}
case "-": {
if (2 > stack.size()) {
throw new RuntimeException("解析异常");
}
value2 = stack.pop();
value1 = stack.pop();
stack.push(value1 - value2);
break;
}
case "*": {
if (2 > stack.size()) {
throw new RuntimeException("解析异常");
}
value2 = stack.pop();
value1 = stack.pop();
stack.push(value1 * value2);
break;
}
case "/": {
if (2 > stack.size()) {
throw new RuntimeException("解析异常");
}
value2 = stack.pop();
value1 = stack.pop();
stack.push(value1 / value2);
break;
}
default: {
stack.push(Integer.parseInt(string));
break;
}
}
}
if (1 != stack.size()) {
throw new RuntimeException("解析异常");
}
return stack.pop();
}
在这里插入图片描述
可以发现，运算的结果是和表达式
1+((2+3)*4)-5的结果一样。
对比传统的算术表达式运算，后缀表达式确实满足运算符的先后顺序，并且计算机执行起来更加简洁方便，只要简单的从左往右遍历表达式，就能计算出结果，避免了使用正则表达式去处理时因为匹配优先级各种字符串匹配的过程。那到底是怎么从一个算术表达式推导出一个后缀表达式的呢？
后缀表达式的推导
同样，后缀表达式的推导也同样有一个规则：这里需要初始化两个辅助工具一个队列和一个堆栈，分别是后缀表达式输出队列（先进先出）和操作符暂存栈（先进后出）。
从左往右依次遍历算术表达式，如果遍历到的元素是数值的话，直接入队到输出队列中，如果遍历到的元素是操作符的话，情况比较复杂一些，需要考虑这些操作运算符的优先级：
如果当前遍历到的操作符是+-的话，因为优先级相对较低，只有在操作符堆栈为空或者栈顶操作符为(的时候才能入栈。如果栈顶操作符的优先级大于或等于当前操作符的话，则将栈顶操作符出栈，并入队到后缀表达式输出队列。在栈顶操作符出栈后，当前操作符继续和新的栈顶操作符比较，以此类推，直到达到入栈标准。
如果当前遍历到的操作符是*/的话，思想和上述+-一样，但是因为*/的优先级相对较高，所以入栈的条件相对较低，只要堆栈为空，或者只要栈顶元素不是*/都能入栈。否则，将栈顶操作符出栈，并入队到后缀表达式输出队列。在栈顶操作符出栈后，当前操作符继续和新的栈顶操作符比较，以此类推，直到达到入栈标准。
这里最特殊的当属操作符()，如果当前遍历到的操作符是(的话，不论什么情况，直接入栈。如果当前遍历到的操作符为)的话，操作符堆栈内距离栈顶最近的那个操作符(和栈顶组成的一个区间内所有的操作符，依次出栈，并入队到后缀表达式输出队列。出栈完毕后，将栈顶的操作符(出栈，并舍去。这也就是后缀表达式明明没有小括号，却同样能实现原本算术表达式中小括号内的运算优先的保证。
在这里插入图片描述
/***
* 将中缀表达式转换为后缀表达式
* */
public String[] parse2rpn(String[] expressionArray) {
Objects.requireNonNull(expressionArray, "算术表达式数组为空");
Queue<String> queue = new LinkedList<>();
Stack<String> stack = new Stack<>();
for (String string : expressionArray) {
if (!"+".equals(string) && !"-".equals(string) && !"*".equals(string) && !"/".equals(string)
&& !"(".equals(string) && !")".equals(string)) {
// 非操作符直接输出到队列
queue.offer(string);
continue;
}
if ("+".equals(string) || "-".equals(string)) {
while (true) {
// 加减符号只有在空栈，或者栈顶操作符为'('的情况下能够入栈
if ((0 >= stack.size() || "(".equals(stack.peek()))) {
stack.push(string);
break;
} else {
queue.offer(stack.pop());
}
}
continue;
}
if ("*".equals(string) || "/".equals(string)) {
while (true) {
// 乘除符号只要栈顶符号不是乘除符号，都能入栈
if ((0 >= stack.size() || (!"*".equals(stack.peek()) && !"/".equals(stack.peek())))) {
stack.push(string);
break;
} else {
queue.offer(stack.pop());
}
}
continue;
}
// 左括号任何情况直接入栈
if ("(".equals(string)) {
stack.push(string);
continue;
}
while (true) {
if (0 >= stack.size()) {
throw new RuntimeException("表达式异常");
}
if (!"(".equals(stack.peek())) {
queue.offer(stack.pop());
} else {
stack.pop();
break;
}
}
}
while (0 < stack.size()) {
queue.offer(stack.pop());
}
return queue.toArray(new String[0]);
}
结束语
后缀表达式在推导过程中，巧妙的运用了数据结构中栈先进后出的特性，将优先级较高的操作符放置在栈顶，在出栈的时候，栈顶的操作符优先入队到输出队列中，这也就满足了从左往右遍历后缀表达式的时候优先级较高的操作符在左侧优先计算。因此，在后续运行的时候就不需要再去考虑优先级问题，从左往右执行运算操作就行。
可以发现，实现从传统算术表达式也到后缀表达式的转换并不难，虽然可读性下降了，但是却能使计算机理解起来简单，降低编写程序的复杂性，提高运行的效率。
文章到这里也该结束了，如果觉得这篇文章对你了解后缀表达式或者在日常解决问题有帮助的话，不胜荣幸。当然，如果对文章有什么疑问，又或者是文章中有什么地方有误或者解释不当，请在评论区留言，一起探讨。
关注我，带你去看编程世界中那些有趣的发现。
在这里插入图片描述
