目录
前言
给你一个字符串"10-6-(10-((3+40.2)+8))*5+8"，你能根据这个字符串中的算式计算出最终的结果吗？有些人说，我根据数字和符号一个一个分析，一个一个new，一个一个加减乘除，当然可以！不过，这样怕是要花费巨长的时间......
所以，我们有好一点的方法来进行计算，实现一个真正能实现的计时器功能吗？当然可以，在这里就利用栈来解决这一类问题。
一、概念引入
栈
栈是一种操作受限的线性表，只允许从一端插入和删除数据，他就像一个木桶，当数据被加进木桶时，数据会被存放到栈的底端，当需要使用数据时，只能从栈顶开始取出数据。简单地说，栈中的数据符合 先入后出，后入先出 的原则。于是我们把数据放入栈中的操作叫做push，从栈中取出数据的操作称为pop，以此来对数据进行操作。
中缀表达式和后缀表达式
在我们日常生活中，最常见的运算表达式如：(3+5)-6+8，10-6-(10-((3+40.2)+8))*5+8这些（小学学过）的表达式，我们就称之为 中缀表达式。中缀表达式的求值是我们最熟悉的，但是这对于计算机来说却犯难了，我们人知道如括号，乘号等具有优先级别的子式会先进行计算，但是计算机要怎么来处理这个问题呢？
于是在前人的研究下，后缀表达式 诞生了，后缀表达式则非常适用于计算机的运算，后缀表达式的运算符主要位于操作数之后，如：
(3+5)-6+8 对应的后缀表达式为：3 5 + 6 - 8 +
10-6-(10-((3+40.2)+8))*5+8 对应的后缀表达式为：10 6 - 10 3 40.2 + 8 + - 5 * - 8 +
这个后缀表达式是什么意思呢？后缀表达式是怎么得出来的呢？后缀表达式到底实现了什么样的功能呢？接下来就对问题一一分析。
二、问题分析
1.利用后缀表达式进行计算
以上方的 (3+5)-6+8 对应的后缀表达式为：3 5 + 6 - 8 + 为例，计算机可以如何利用这个表达式对这个算式进行计算呢？
第一步：从左至右对后缀表达式进行扫描，将扫描出来的数字压入堆栈，这里就将3和5压入堆栈；
第二步，遇到运算符，弹出栈顶元素和次顶元素，这里就是5和3，利用运算符计算值，这里就是3+5（这里一定注意，运算是次顶元素在前，栈顶元素在后，避免减法和除法求反），得到结果8，再将8入栈。
第三步：接下来又扫描到了数字，此时又将该数字压入栈，这里是将6压入栈
第四步：接下来，遇到了运算符，又将栈中的两个数字进行运算，算出的结果放入栈中，如此循环，当运算到最后一个数字时，栈中最后一个数字即为最后的结果。
利用后缀表达式，计算机的运算就变得非常简单了，就可以根据表达式精确地运算等式的值。所以现在的问题就是，如何将中缀表达式转换为后缀表达式呢？
2.中缀表达式转后缀表达式
中缀表达式如何转为后缀表达式呢？具体步骤如下：
第一步：初始化两个栈：运算符利用栈2储存，数字利用栈1进行储存；
第二步：从左至右扫描中缀表达式； 遇到操作数时，将其压至栈1；
第三步：遇到运算符时，对运算符的优先级进行判断：
1. 如果栈2为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
2. 否则，若优先级比栈顶运算符的高，也将运算符压入栈1；
3. 否则，将栈2顶的运算符弹出并压入到栈1中，再次循环与栈2中新的栈顶运算符相比较；
第四步：遇到括号时，进行判断：
1. 如果是左括号“(”，则直接压入栈2
2. 如果是右括号“)”，则依次弹出栈2栈顶的运算符，并压入栈1，直到遇到左括号为止，此时将这一对括号丢弃.
第五步：重复判断，直至表达式的最右边。
最后一步：判断完成之后，将栈2剩余的运算符依次pop出并且压入栈1，完成之后，依次pop出栈1的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
二、代码实现
中缀表达式转后缀表达式
public static String toReversePolish(String expression) {
Stack<String> stack1 = new Stack<>();
Stack<String> stack2 = new Stack<>();
String number = "";
for (int i = 0; i < expression.length();) {
boolean isAll = false;
while((expression.charAt(i)>='0' && expression.charAt(i) <= '9') || expression.charAt(i)=='.') {
number += expression.charAt(i);
i++;
if (i == expression.length()) {
isAll = true;
break;
}
}
if (!number.isEmpty()) {
stack2.push(new StringBuffer(number).reverse().toString());
number = "";
}
if (isAll) {
break;
}
if (expression.charAt(i) == ')') {
while (!stack1.peek().equals("(")) {
stack2.push(stack1.pop());
}
stack1.pop();
i++;
continue;
}
while(!(expression.charAt(i)>='0' && expression.charAt(i) <= '9')) {
char symbol = expression.charAt(i);
if ((stack1.size() == 0) || (stack1.peek().equals("(")) || (symbol=='(')) {
stack1.push(symbol+"");
i++;
break;
}
if ((symbol == '+') || (symbol == '-')) {
stack2.push(stack1.pop());
continue;
} else {
if ((stack1.peek().equals("+")) || (stack1.peek().equals("-"))) {
stack1.push(symbol+"");
i++;
break;
}
if ((stack1.peek().equals("*")) || (stack1.peek().equals("/"))) {
stack2.push(stack1.pop());
continue;
}
}
}
}
while(stack1.size() != 0) {
stack2.push(stack1.pop());
}
String s1 = "";
while(stack2.size() != 0) {
s1 += stack2.pop();
if (stack2.size() != 0) {
s1 += " ";
}
}
return new StringBuffer(s1).reverse().toString();
}计算功能的实现
public static void main(String[] args) {
String ReversePolish = toReversePolish("10-6-(10-((3+40.2)+8))*5+8");
//6 10 3 40.2 + 8 + - 5 * - 8 +
String[] expression = ReversePolish.split(" ");
Stack<Double> stack = new Stack<>();
for (int i = 0; i < expression.length; i++) {
switch (expression[i]) {
case "+" : {
double num1 = stack.pop();
double num2 = stack.pop();
double result = num1+num2;
stack.push(result);
break;
}
case "-" : {
double num1 = stack.pop();
double num2 = stack.pop();
double result = num2-num1;
stack.push(result);
break;
}
case "*" : {
double num1 = stack.pop();
double num2 = stack.pop();
double result = num1*num2;
stack.push(result);
break;
}
case "/" : {
double num1 = stack.pop();
double num2 = stack.pop();
double result = num2/num1;
stack.push(result);
break;
}
default: {
Double in = Double.parseDouble(expression[i]);
stack.push(in);
}
}
}
System.out.println(stack.pop());
}总结
以上就是利用Java语言处理中缀表达式和后缀表达式，实现计算功能的过程。在Java中处理问题时，会产生一些独有想法和实现方式，不妨再继续动手试一试？