这几天想写一个Android的计算器，所以先写好中缀表达式到后缀表达式的计算。
例如：中缀表达式(8+9*10)-4/2+3
我们可以进行如下操作：
1、将每个操作符对应的两个操作数用括号括上(((8+(9*10))-(4/2))+3)
2、将操作符移到对应的括号外(((8(910*)+)(42)/)-3)+
3、去掉括号即可 8910*+42/-3+
是不是很简单，这样我们就讲一个中缀表达式转换成论文后缀表达式。
那么计算机中是怎样进行的呢？
转换的整体流程如下：
中缀表达式转后缀表达式的方法：
1.遇到操作数：直接输出(添加到后缀表达式中)
2.栈为空时，遇到运算符，直接入栈
3.遇到左括号：将其入栈
4.遇到右括号：执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，左括号不输出。
5.遇到其他运算符：加减乘除：弹出所有优先级大于或者等于该运算符的栈顶元素，然后将该运算符入栈
6.最终将栈中的元素依次出栈，输出。
下面是我写得一个示例代码：
package cn.tzy.calculator;import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Stack;/*** Created by gchx on 2015/2/9.*/
public class Calculator {private Map<String, Integer> priority;//操作符优先级Mappublic Calculator() {initPriority();}private void initPriority() {this.priority = new HashMap<>();//这里的#号是操作符堆栈中的栈底元素，是为了程序方便处理而添加的this.priority.put("#", 0);this.priority.put("+", 1);this.priority.put("-", 1);this.priority.put("*", 2);this.priority.put("/", 2);}//得到操作符的优先级public int getPriority(String operator) {//这里括号进行特殊处理if (operator.matches("[()]")) {return -1;} else {return priority.get(operator);}}//判断优先级高低private boolean isPrior(String one, String another) {return getPriority(one) <= getPriority(another);}//得到栈顶元素private <T> T getTopEle(Stack<T> stack) {if (stack == null) {return null;} else {return stack.get(stack.size() - 1);}}/*** @param expression 算数表达式* @return* 将中缀表达式转换为后缀表达式*/public Queue<String> toSuffix(String expression) {Queue<String> operandQueue = new LinkedList<>();//操作数队列Stack<String> operatorStack = new Stack<>();//操作符堆栈operatorStack.push("#");String current = "";String operator = "";String number = "";int start = 0;int end = 0;for (int i = 0; i < expression.length(); i++) {current = String.valueOf(expression.charAt(i));// 如果是数字，末尾标记end++if (current.matches("[\\d\\.]")) {// 如果数字是最后一个字符，直接将其入队列if (i == expression.length() - 1) {operandQueue.add(current);} else {end++;}} else {// 如果是字符// 如果是左括号，将其入栈if (current.equals("(")) {operatorStack.push(current);} else {// 如果是右括号和其它运算符，先将前面的数字入队列number = expression.substring(start, end);if (!number.isEmpty()) {operandQueue.add(number);}// 如果是右括号，执行出栈操作，并将出栈的元素入队列，直到弹出栈的是左括号，左括号直接出栈if (current.equals(")")) {while (!getTopEle(operatorStack).equals("(")) {operandQueue.add(operatorStack.pop());}operatorStack.pop();} else {// 如果是其它运算符，弹出所有优先级大于或者等于该运算符的栈顶元素，然后将该运算符入栈operator = current;while (isPrior(operator, getTopEle(operatorStack))) {operandQueue.add(operatorStack.pop());}operatorStack.push(operator);}}// 将指向数字的首尾指针加1start = end = i + 1;}}for (int i = operatorStack.size() - 1; i > 0; i--) {operandQueue.add(operatorStack.pop());}return operandQueue;}/*** @param expression 算数表达式* @return* 得到表达式的结果*/public double getResult(String expression) {Queue<String> suffixQueue = toSuffix(expression);Stack<String> suffixStack = new Stack<String>();String current = "";double frontOperand;double backOperand;double value = 0;for (int i = suffixQueue.size(); i > 0; i--) {current = suffixQueue.poll();//如果是数字，入栈if (current.matches("^\\d+(\\.\\d+)*$")) {suffixStack.push(current);} else {backOperand = Double.valueOf(suffixStack.pop());frontOperand = Double.valueOf(suffixStack.pop());if (current.equals("+")) {value = frontOperand + backOperand;} else if (current.equals("-")) {value = frontOperand - backOperand;} else if (current.equals("*")) {value = frontOperand * backOperand;} else if (current.equals("/")) {try {value = frontOperand / backOperand;} catch (Exception e) {return 0;}}suffixStack.push(String.valueOf(value));}}String result = suffixStack.get(0);return Double.valueOf(result);}}单元测试代码如下：
package cn.tzy.calculator;import java.util.Queue;import org.junit.Assert;
import org.junit.Test;public class CalculatorTest {private Calculator calculator;private String infix;public CalculatorTest() {this.calculator = new Calculator();this.infix = "(8+9*10)-4/2+3";}@Testpublic void testToSuffix() {Queue<String> suffix = calculator.toSuffix(infix);for (int i = suffix.size(); i > 0; i--) {System.out.print("(" + suffix.poll() + ")");}}@Testpublic void testGetResult() {double result = calculator.getResult(infix);Assert.assertEquals(result, 99, 0);}
}