第 5 章栈（二）-阿里云开发者社区

4、前缀中缀后缀表达式

4.1、前缀表达式(波兰表达式)

4.1.1、前缀表达式

前缀表达式又称波兰式，前缀表达式的运算符位于操作数之前
举例说明： (3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6

4.1.2、前缀表达式的计算机求值

从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素和次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果
例如：(3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6 , 针对前缀表达式求值步骤如下:

从右至左扫描，将6、5、4、3压入堆栈
遇到+运算符，因此弹出3和4（3为栈顶元素，4为次顶元素），计算出3+4的值，得7，再将7入栈
接下来是×运算符，因此弹出7和5，计算出7×5=35，将35入栈
最后是-运算符，计算出35-6的值，即29，由此得出最终结果

4.2、中缀表达式

中缀表达式就是常见的运算表达式，如(3+4)×5-6
中缀表达式的求值是我们人最熟悉的，但是对计算机来说却不好操作(前面我们讲的案例就能看的这个问题，因为中缀表达式存在运算符优先级的问题)，因此，在计算结果时，往往会将中缀表达式转成其它表达式来操作(一般转成后缀表达式)

4.3、后缀表达式

4.3.1、后缀表达式

后缀表达式又称逆波兰表达式，与前缀表达式相似，只是运算符位于操作数之后
中缀表达式举例说明： (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 –
再比如:

正常的表达式	逆波兰表达式
a+b	a b +
a+(b-c)	a b c - +
a+(b-c)*d	a b c – d * +
a+d*(b-c)	a d b c - * +
a=1+3	a 1 3 + =

4.3.2、后缀表达式的计算机求值

从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素和栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果

例如: (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 - , 针对后缀表达式求值步骤如下:

从左至右扫描，将3和4压入堆栈；
遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈；
将5入栈；
接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈；
将6入栈；
最后是-运算符，计算出35-6的值，即29，由此得出最终结果

5、逆波兰计算器

5.1、计算器说明

输入一个逆波兰表达式(后缀表达式)，使用栈(Stack)，计算其结果
支持小括号和多位数整数，因为这里我们主要讲的是数据结构，因此计算器进行简化，只支持对整数的计算

5.2、代码思路

计算后缀表达式无需考虑运算符优先级问题，所以只需要一个数栈即可
分为两种情况：

遇到数：压入数栈
遇到运算符：从数栈中弹出两个数，进行计算，计算结果压入数栈

何时计算完成？处理完表达式就代表计算完成

5.3、代码实现

出栈的两个数：num2 和 num1

num2 先出栈，所以 num2 是减数或除数
num1 后出栈，所以 num1 是被减数或被除数

public class PolandNotation {
 public static void main(String[] args) {
  //先定义给逆波兰表达式
  // 4 * 5 - 8 + 60 + 8 / 2 => 4 5 * 8 - 60 + 8 2 / + 
  //说明为了方便，逆波兰表达式 的数字和符号使用空格隔开
  String suffixExpression = "4 5 * 8 - 60 + 8 2 / +"; // 76
  //思路
  //1. 先将逆波兰表达式 => 放到ArrayList中
  //2. 将 ArrayList 传递给一个方法，遍历 ArrayList 配合栈 完成计算
  List<String> list = getListString(suffixExpression);
  System.out.println("rpnList=" + list);
  int res = calculate(list);
  System.out.println("计算的结果是=" + res);
 }
 //将一个逆波兰表达式， 依次将数据和运算符 放入到 ArrayList中
 public static List<String> getListString(String suffixExpression) {
  //将 suffixExpression 分割
  String[] split = suffixExpression.split(" ");
  List<String> list = new ArrayList<String>();
  for(String ele: split) {
   list.add(ele);
  }
  return list;
 }
 //完成对逆波兰表达式的运算
 /*
  * 1)从左至右扫描，将3和4压入堆栈；
  2)遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈；
  3)将5入栈；
  4)接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈；
  5)将6入栈；
  6)最后是-运算符，计算出35-6的值，即29，由此得出最终结果
  */
 public static int calculate(List<String> ls) {
  // 创建给栈, 只需要一个栈即可
  Stack<String> stack = new Stack<String>();
  // 遍历 ls
  for (String item : ls) {
   // 这里使用正则表达式来取出数
   if (item.matches("\\d+")) { // 匹配的是多位数
    // 入栈
    stack.push(item);
   } else {
    // pop出两个数，并运算， 再入栈
    int num2 = Integer.parseInt(stack.pop());
    int num1 = Integer.parseInt(stack.pop());
    int res = 0;
    if (item.equals("+")) {
     res = num1 + num2;
    } else if (item.equals("-")) {
     res = num1 - num2;
    } else if (item.equals("*")) {
     res = num1 * num2;
    } else if (item.equals("/")) {
     res = num1 / num2;
    } else {
     throw new RuntimeException("运算符有误");
    }
    //把res 入栈
    stack.push("" + res);
   }
  }
  //最后留在stack中的数据是运算结果
  return Integer.parseInt(stack.pop());
 }
}

程序运行结果

rpnList=[4, 5, *, 8, -, 60, +, 8, 2, /, +]
计算的结果是=76

6、中缀表达式转后缀表达式

6.1、代码思路

大家看到，后缀表达式适合计算式进行运算，但是人却不太容易写出来，尤其是表达式很长的情况下，因此在开发中，我们需要将中缀表达式转成后缀表达式。
具体步骤如下:

初始化两个栈：运算符栈operStack和储存中间结果的栈tempStack；
从左至右扫描中缀表达式；
遇到操作数时，将其压tempStack；
遇到运算符时，比较其与operStack栈顶运算符的优先级：
1.如果operStack为空，或栈顶运算符为左括号“(”，则直接将此运算符入tempStack栈（分如下两种情况）

1.operStack 栈顶为空：之前的优先级别高的运算已经处理完成，已经得到了一个结果，将当前运算符直接压入 operStack 栈即可

2.operStack 栈顶为左括号：我都挨着左括号了，我要和它同生共死！当把我从operStack 出栈，用于运算后，这对括号中的表达式的值也就计算出来了

2.如果当前运算符优先级比栈顶运算符的高，也将运算符压入tempStack （当前运算符优先级高，先执行运算）

3.否则，当前运算符优先级 <= 栈顶运算符优先级，将operStack栈顶的运算符弹出并压入到tempStack中（operStack 栈顶运算符优先级高，先执行运算），再次转到(4.1)与operStack中新的栈顶运算符相比较（分如下两种情况）；

1. 一直循环，将 tempStack 栈顶元素取出，直到在 operStack 栈中找到比当前运算符优先级高的运算符，让其先执行运算

如果在 tempStack 栈中找不到比当前运算符优先级高的运算符，则会直接将 2.operStack 栈掏空，然后将当前运算符压入 tempStack 栈中（放在栈底）

5.遇到括号时：

1.如果是左括号“(”，则直接压入operStack，等待与其配对的右括号，因为括号中的表达式需要优先运算

2.如果是右括号“)”，则依次弹出operStack栈顶的运算符，并压入tempStack，直到遇到左括号为止，此时将这一对括号丢弃（此时括号内的运算完成，并将结果压入了tempStack）

6.重复步骤2至5，直到表达式的最右边

7.将operStack中剩余的运算符依次弹出并压入tempStack（operStack 栈中剩下的运算都是优先级相同的运算符，按顺序执行即可）

8.依次弹出tempStack中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式

6.2、举例说明

举例说明：将中缀表达式“1+((2+3)×4)-5”转换为后缀表达式的过程如下
因此结果为：“1 2 3 + 4 × + 5 –”

扫描到的元素 tempStack(栈底->栈顶) operStack(栈底->栈顶) 说明

6.3、代码实现

将中缀表达式转为对应的 List ：将数字和运算符分开，存储在 List<String> 对象中

// 方法：将 中缀表达式转成对应的List
// s="1+((2+3)×4)-5";
public static List<String> toInfixExpressionList(String s) {
    // 定义一个List,存放中缀表达式 对应的内容
    List<String> ls = new ArrayList<String>();
    int i = 0; // 这时是一个指针，用于遍历 中缀表达式字符串
    String str; // 对多位数的拼接
    char c; // 每遍历到一个字符，就放入到c
    do {
        // 如果c是一个非数字，我需要加入到ls
        if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {
            ls.add("" + c);
            i++; // i需要后移
        } else { // 如果是一个数，需要考虑多位数
            str = ""; // 先将str 置成"" '0'[48]->'9'[57]
            while (i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) {
                str += c;// 拼接
                i++;
            }
            ls.add(str);
        }
    } while (i < s.length());
    return ls;// 返回
}

将中缀表达式（List）转为后缀表达式（List）

如果是一个数，加入tempList

如果是 ( ，则直接入operStack（括号内的表达式优先计算）

如果是 ) ，则依次弹出 operStack 栈顶的运算符，并压入 tempList ，直到遇到左括号为止，此时将这一对括号丢弃（括号内的表达式优先计算）

否则比较当前运算符和栈顶运算符优先级

当前运算符优先级 > 栈顶运算符，将当前运算符压入 operStack 栈中（当前运算符优先级较高，先进行运算）
当前运算符优先级 <= 栈顶运算符，将 operStack 栈顶运算符取出，压入 tempList 中，再次对新的栈顶元素进行优先级判断（之前的运算符优先级较高，先进行运算）

// 即 ArrayList [1,+,(,(,2,+,3,),*,4,),-,5] =》 ArrayList [1,2,3,+,4,*,+,5,–]
// 方法：将得到的中缀表达式对应的List => 后缀表达式对应的List
public static List<String> parseSuffixExpreesionList(List<String> ls) {
    // 定义两个栈
    Stack<String> operStack = new Stack<String>(); // 符号栈
    // 说明：因为tempList 这个栈，在整个转换过程中，没有pop操作，而且后面我们还需要逆序输出
    // 因此比较麻烦，这里我们就不用 Stack<String> 直接使用 List<String> tempList
    // Stack<String> tempStack = new Stack<String>(); // 储存中间结果的栈tempStack
    List<String> tempList = new ArrayList<String>(); // 储存中间结果的tempList
    // 遍历ls
    for (String item : ls) {
        if (item.matches("\\d+")) { // 如果是一个数，加入tempList
            tempList.add(item);
        } else if (item.equals("(")) { // 如果是 ( ，则直接入operStack
            operStack.push(item);
        } else if (item.equals(")")) { // 如果是 ) ，则将括号内的值算出，并压入 tempList）
            // 如果是右括号“)”，则依次弹出operStack栈顶的运算符，并压入tempList，直到遇到左括号为止，此时将这一对括号丢弃
            while (!operStack.peek().equals("(")) {
                tempList.add(operStack.pop());
            }
            operStack.pop();// !!! 将 ( 弹出 s1栈， 消除小括号
        } else { // 否则比较当前运算符和栈顶运算符优先级
            // 当item的优先级小于等于operStack栈顶运算符,
            // 将operStack栈顶的运算符弹出并加入到tempList中，再次转到(4.1)与operStack中新的栈顶运算符相比较
            // 问题：我们缺少一个比较优先级高低的方法
            while (operStack.size() != 0 && Operation.getValue(operStack.peek()) >= Operation.getValue(item)) {
                tempList.add(operStack.pop());
            }
            // 还需要将item压入栈
            operStack.push(item);
        }
    }
    // 将operStack中剩余的运算符依次弹出并加入tempList
    while (operStack.size() != 0) {
        tempList.add(operStack.pop());
    }
    return tempList; // 注意因为是存放到List, 因此按顺序输出就是对应的后缀表达式对应的List
}

测试代码：

将中缀表达式转为对应的 List
将中缀表达式 List 转为后缀表达式 List
调用逆波兰计算器执行计算

public static void main(String[] args) {
    // 完成将一个中缀表达式转成后缀表达式的功能
    // 说明
    // 1. 1+((2+3)×4)-5 => 转成 1 2 3 + 4 × + 5 –
    // 2. 因为直接对str 进行操作，不方便，因此 先将 "1+((2+3)×4)-5" =》 中缀的表达式对应的List
    // 即 "1+((2+3)×4)-5" => ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]
    // 3. 将得到的中缀表达式对应的List => 后缀表达式对应的List
    // 即 ArrayList [1,+,(,(,2,+,3,),*,4,),-,5] =》 ArrayList [1,2,3,+,4,*,+,5,–]
    String expression = "1+((2+3)*4)-5";// 注意表达式
    List<String> infixExpressionList = toInfixExpressionList(expression);
    System.out.println("中缀表达式对应的List=" + infixExpressionList); // ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]
    List<String> suffixExpreesionList = parseSuffixExpreesionList(infixExpressionList);
    System.out.println("后缀表达式对应的List" + suffixExpreesionList); // ArrayList [1,2,3,+,4,*,+,5,–]
    System.out.printf("expression=%d", calculate(suffixExpreesionList)); // ?
}

程序运行结果

中缀表达式对应的List=[1, +, (, (, 2, +, 3, ), *, 4, ), -, 5]
后缀表达式对应的List[1, 2, 3, +, 4, *, +, 5, -]
expression=16

6.4、中缀表达式转后缀表达式完整代码

public class PolandNotation {
 public static void main(String[] args) {
  // 完成将一个中缀表达式转成后缀表达式的功能
  // 说明
  // 1. 1+((2+3)×4)-5 => 转成 1 2 3 + 4 × + 5 –
  // 2. 因为直接对str 进行操作，不方便，因此 先将 "1+((2+3)×4)-5" =》 中缀的表达式对应的List
  // 即 "1+((2+3)×4)-5" => ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]
  // 3. 将得到的中缀表达式对应的List => 后缀表达式对应的List
  // 即 ArrayList [1,+,(,(,2,+,3,),*,4,),-,5] =》 ArrayList [1,2,3,+,4,*,+,5,–]
  String expression = "1+((2+3)*4)-5";// 注意表达式
  List<String> infixExpressionList = toInfixExpressionList(expression);
  System.out.println("中缀表达式对应的List=" + infixExpressionList); // ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]
  List<String> suffixExpreesionList = parseSuffixExpreesionList(infixExpressionList);
  System.out.println("后缀表达式对应的List" + suffixExpreesionList); // ArrayList [1,2,3,+,4,*,+,5,–]
  System.out.printf("expression=%d", calculate(suffixExpreesionList)); // ?
 }
 // 方法：将 中缀表达式转成对应的List
 // s="1+((2+3)×4)-5";
 public static List<String> toInfixExpressionList(String s) {
  // 定义一个List,存放中缀表达式 对应的内容
  List<String> ls = new ArrayList<String>();
  int i = 0; // 这时是一个指针，用于遍历 中缀表达式字符串
  String str; // 对多位数的拼接
  char c; // 每遍历到一个字符，就放入到c
  do {
   // 如果c是一个非数字，我需要加入到ls
   if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {
    ls.add("" + c);
    i++; // i需要后移
   } else { // 如果是一个数，需要考虑多位数
    str = ""; // 先将str 置成"" '0'[48]->'9'[57]
    while (i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) {
     str += c;// 拼接
     i++;
    }
    ls.add(str);
   }
  } while (i < s.length());
  return ls;// 返回
 }
 // 即 ArrayList [1,+,(,(,2,+,3,),*,4,),-,5] =》 ArrayList [1,2,3,+,4,*,+,5,–]
 // 方法：将得到的中缀表达式对应的List => 后缀表达式对应的List
 public static List<String> parseSuffixExpreesionList(List<String> ls) {
  // 定义两个栈
  Stack<String> operStack = new Stack<String>(); // 符号栈
  // 说明：因为tempList 这个栈，在整个转换过程中，没有pop操作，而且后面我们还需要逆序输出
  // 因此比较麻烦，这里我们就不用 Stack<String> 直接使用 List<String> tempList
  // Stack<String> tempStack = new Stack<String>(); // 储存中间结果的栈tempStack
  List<String> tempList = new ArrayList<String>(); // 储存中间结果的tempList
  // 遍历ls
  for (String item : ls) {
   if (item.matches("\\d+")) { // 如果是一个数，加入tempList
    tempList.add(item);
   } else if (item.equals("(")) { // 如果是 ( ，则直接入operStack
    operStack.push(item);
   } else if (item.equals(")")) { // 如果是 ) ，则将括号内的值算出，并压入 tempList）
    // 如果是右括号“)”，则依次弹出operStack栈顶的运算符，并压入tempList，直到遇到左括号为止，此时将这一对括号丢弃
    while (!operStack.peek().equals("(")) {
     tempList.add(operStack.pop());
    }
    operStack.pop();// !!! 将 ( 弹出 s1栈， 消除小括号
   } else { // 否则比较当前运算符和栈顶运算符优先级
    // 当item的优先级小于等于operStack栈顶运算符,
    // 将operStack栈顶的运算符弹出并加入到tempList中，再次转到(4.1)与operStack中新的栈顶运算符相比较
    // 问题：我们缺少一个比较优先级高低的方法
    while (operStack.size() != 0 && Operation.getValue(operStack.peek()) >= Operation.getValue(item)) {
     tempList.add(operStack.pop());
    }
    // 还需要将item压入栈
    operStack.push(item);
   }
  }
  // 将operStack中剩余的运算符依次弹出并加入tempList
  while (operStack.size() != 0) {
   tempList.add(operStack.pop());
  }
  return tempList; // 注意因为是存放到List, 因此按顺序输出就是对应的后缀表达式对应的List
 }
 // 完成对逆波兰表达式的运算
 /*
  * 1)从左至右扫描，将3和4压入堆栈； 2)遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈； 3)将5入栈；
  * 4)接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈； 5)将6入栈； 6)最后是-运算符，计算出35-6的值，即29，由此得出最终结果
  */
 public static int calculate(List<String> ls) {
  // 创建给栈, 只需要一个栈即可
  Stack<String> stack = new Stack<String>();
  // 遍历 ls
  for (String item : ls) {
   // 这里使用正则表达式来取出数
   if (item.matches("\\d+")) { // 匹配的是多位数
    // 入栈
    stack.push(item);
   } else {
    // pop出两个数，并运算， 再入栈
    int num2 = Integer.parseInt(stack.pop());
    int num1 = Integer.parseInt(stack.pop());
    int res = 0;
    if (item.equals("+")) {
     res = num1 + num2;
    } else if (item.equals("-")) {
     res = num1 - num2;
    } else if (item.equals("*")) {
     res = num1 * num2;
    } else if (item.equals("/")) {
     res = num1 / num2;
    } else {
     throw new RuntimeException("运算符有误");
    }
    // 把res 入栈
    stack.push("" + res);
   }
  }
  // 最后留在stack中的数据是运算结果
  return Integer.parseInt(stack.pop());
 }
}
//编写一个类 Operation 可以返回一个运算符 对应的优先级
class Operation {
 private static int LEFT_BRACKET  = 0;
 private static int ADD = 1;
 private static int SUB = 1;
 private static int MUL = 2;
 private static int DIV = 2;
 // 写一个方法，返回对应的优先级数字
 public static int getValue(String operation) {
  int result = 0;
  switch (operation) {
  case "(":
   result = LEFT_BRACKET;
   break;
  case "+":
   result = ADD;
   break;
  case "-":
   result = SUB;
   break;
  case "*":
   result = MUL;
   break;
  case "/":
   result = DIV;
   break;
  default:
   System.out.println("不存在该运算符" + operation);
   break;
  }
  return result;
 }
}

7、完整版逆波兰计算器

public class ReversePolishMultiCalc {
  /**
     * 匹配 + - * / ( ) 运算符
     */
    static final String SYMBOL = "\\+|-|\\*|/|\\(|\\)";
    static final String LEFT = "(";
    static final String RIGHT = ")";
    static final String ADD = "+";
    static final String MINUS= "-";
    static final String TIMES = "*";
    static final String DIVISION = "/";
    /**
     * 加減 + -
     */
    static final int LEVEL_01 = 1;
    /**
     * 乘除 * /
     */
    static final int LEVEL_02 = 2;
    /**
     * 括号
     */
    static final int LEVEL_HIGH = Integer.MAX_VALUE;
    static Stack<String> stack = new Stack<>();
    static List<String> data = Collections.synchronizedList(new ArrayList<String>());
    /**
     * 去除所有空白符
     * @param s
     * @return
     */
    public static String replaceAllBlank(String s ){
        // \\s+ 匹配任何空白字符，包括空格、制表符、换页符等等, 等价于[ \f\n\r\t\v]
        return s.replaceAll("\\s+","");
    }
    /**
     * 判断是不是数字 int double long float
     * @param s
     * @return
     */
    public static boolean isNumber(String s){
        Pattern pattern = Pattern.compile("^[-\\+]?[.\\d]*$");
        return pattern.matcher(s).matches();
    }
    /**
     * 判断是不是运算符
     * @param s
     * @return
     */
    public static boolean isSymbol(String s){
        return s.matches(SYMBOL);
    }
    /**
     * 匹配运算等级
     * @param s
     * @return
     */
    public static int calcLevel(String s){
        if("+".equals(s) || "-".equals(s)){
            return LEVEL_01;
        } else if("*".equals(s) || "/".equals(s)){
            return LEVEL_02;
        }
        return LEVEL_HIGH;
    }
    /**
     * 匹配
     * @param s
     * @throws Exception
     */
    public static List<String> doMatch (String s) throws Exception{
        if(s == null || "".equals(s.trim())) throw new RuntimeException("data is empty");
        if(!isNumber(s.charAt(0)+"")) throw new RuntimeException("data illeagle,start not with a number");
        s = replaceAllBlank(s);
        String each;
        int start = 0;
        for (int i = 0; i < s.length(); i++) {
            if(isSymbol(s.charAt(i)+"")){
                each = s.charAt(i)+"";
                //栈为空，(操作符，或者 操作符优先级大于栈顶优先级 && 操作符优先级不是( )的优先级 及是 ) 不能直接入栈
                if(stack.isEmpty() || LEFT.equals(each)
                        || ((calcLevel(each) > calcLevel(stack.peek())) && calcLevel(each) < LEVEL_HIGH)){
                    stack.push(each);
                }else if( !stack.isEmpty() && calcLevel(each) <= calcLevel(stack.peek())){
                    //栈非空，操作符优先级小于等于栈顶优先级时出栈入列，直到栈为空，或者遇到了(，最后操作符入栈
                    while (!stack.isEmpty() && calcLevel(each) <= calcLevel(stack.peek()) ){
                        if(calcLevel(stack.peek()) == LEVEL_HIGH){
                            break;
                        }
                        data.add(stack.pop());
                    }
                    stack.push(each);
                }else if(RIGHT.equals(each)){
                    // ) 操作符，依次出栈入列直到空栈或者遇到了第一个)操作符，此时)出栈
                    while (!stack.isEmpty() && LEVEL_HIGH >= calcLevel(stack.peek())){
                        if(LEVEL_HIGH == calcLevel(stack.peek())){
                            stack.pop();
                            break;
                        }
                        data.add(stack.pop());
                    }
                }
                start = i ;    //前一个运算符的位置
            }else if( i == s.length()-1 || isSymbol(s.charAt(i+1)+"") ){
                each = start == 0 ? s.substring(start,i+1) : s.substring(start+1,i+1);
                if(isNumber(each)) {
                    data.add(each);
                    continue;
                }
                throw new RuntimeException("data not match number");
            }
        }
        //如果栈里还有元素，此时元素需要依次出栈入列，可以想象栈里剩下栈顶为/，栈底为+，应该依次出栈入列，可以直接翻转整个stack 添加到队列
        Collections.reverse(stack);
        data.addAll(new ArrayList<>(stack));
        System.out.println(data);
        return data;
    }
    /**
     * 算出结果
     * @param list
     * @return
     */
    public static Double doCalc(List<String> list){
        Double d = 0d;
        if(list == null || list.isEmpty()){
            return null;
        }
        if (list.size() == 1){
            System.out.println(list);
            d = Double.valueOf(list.get(0));
            return d;
        }
        ArrayList<String> list1 = new ArrayList<>();
        for (int i = 0; i < list.size(); i++) {
            list1.add(list.get(i));
            if(isSymbol(list.get(i))){
                Double d1 = doTheMath(list.get(i - 2), list.get(i - 1), list.get(i));
                list1.remove(i);
                list1.remove(i-1);
                list1.set(i-2,d1+"");
                list1.addAll(list.subList(i+1,list.size()));
                break;
            }
        }
        doCalc(list1);
        return d;
    }
    /**
     * 运算
     * @param s1
     * @param s2
     * @param symbol
     * @return
     */
    public static Double doTheMath(String s1,String s2,String symbol){
        Double result ;
        switch (symbol){
            case ADD : result = Double.valueOf(s1) + Double.valueOf(s2); break;
            case MINUS : result = Double.valueOf(s1) - Double.valueOf(s2); break;
            case TIMES : result = Double.valueOf(s1) * Double.valueOf(s2); break;
            case DIVISION : result = Double.valueOf(s1) / Double.valueOf(s2); break;
            default : result = null;
        }
        return result;
    }
    public static void main(String[] args) {
        //String math = "9+(3-1)*3+10/2";
        String math = "12.8 + (2 - 3.55)*4+10/5.0";
        try {
            doCalc(doMatch(math));
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

第 5 章栈（二）

4、前缀中缀后缀表达式

4.1、前缀表达式(波兰表达式)

4.1.1、前缀表达式

4.1.2、前缀表达式的计算机求值

4.2、中缀表达式

4.3、后缀表达式

4.3.1、后缀表达式

4.3.2、后缀表达式的计算机求值

5、逆波兰计算器

5.1、计算器说明

5.2、代码思路

5.3、代码实现

6、中缀表达式转后缀表达式

6.1、代码思路

6.2、举例说明

6.3、代码实现

6.4、中缀表达式转后缀表达式完整代码

7、完整版逆波兰计算器

热门文章

最新文章

相关课程

相关电子书

第 5 章 栈（二）

4、前缀 中缀 后缀表达式

4.1、前缀表达式(波兰表达式)

4.1.1、前缀表达式

4.1.2、前缀表达式的计算机求值

4.2、中缀表达式

4.3、后缀表达式

4.3.1、后缀表达式

4.3.2、后缀表达式的计算机求值

5、逆波兰计算器

5.1、计算器说明

5.2、代码思路

5.3、代码实现

6、中缀表达式转后缀表达式

6.1、代码思路

6.2、举例说明

6.3、代码实现

6.4、中缀表达式转后缀表达式完整代码

7、完整版逆波兰计算器

热门文章

最新文章

相关课程

相关电子书

第 5 章栈（二）

4、前缀中缀后缀表达式