中缀表达式转后缀表达式(Java代码实现)
后缀表达式求值
后缀表达式又叫逆波兰表达式，其求值过程能够用到栈来辅助存储。例如要求值的后缀表达式为：1 2 3 + 4 * + 5 -，则求值过程以下：算法
- 遍历表达式，遇到数字时直接入栈，栈结构以下
2. 接着读到 “+”操做符，则将栈顶和次栈顶元素出栈与操做符进行运算，执行 2 + 3操做，并将结果5压入栈中，此时栈结构以下express
3. 继续读到4，是数字则直接压栈，此时栈结构以下测试
4. 继续向后读取，此时读取到操做符“*”，则将栈顶和次栈顶元素出栈与操做符进行运算，即执行 5 * 4 ，而后将结果20压入栈中，此时栈结构以下spa
5. 继续向后读取，此时读到操做符“+”，则将栈顶和次栈顶元素出栈与操做符进行运算，即执行1 + 20，而后将结果21压入栈中，此时栈结构以下3d
6. 继续向后读取，此时读到数字5，则直接将数字压栈，栈结构以下指针
7. 读取到最后一个为操做符，将栈顶和次栈顶元素出栈与操做符进行运算，即执行 21- 5（注意顺序 次栈顶-栈顶）,而后将结果16压入栈中，此时栈结构以下code
此时栈顶元素即为表达式的结果。（注：为方便理解，这里栈顶指针向下移动后，上面元素直接去掉了，实际状况数据还会存在对应位置，只是经过栈顶指针读取不到，等待GC）blog
中缀表达式转后缀表达式
中缀表达式为咱们人类能识别的方式，然后缀表达式是计算机进行运算的方式（即咱们上述的过程)。字符串
转换规则
1）咱们使用一个stack栈结构存储操做符，用一个List结构存储后缀表达式结果get
2）首先读取到数字，直接存入list中
3）当读取到左括号"("时，直接压栈，当读取到运算符时，分两种状况讨论
a.当运算符栈为空或者栈顶操做符的优先级小于当前运算符优先级时(如+和-的优先级低于 * 和 /)，直接入栈
b.当运算符不为空时且栈顶操做符的优先级大于或等于当前运算符优先级时，循环执行出栈操做并加入list中，直到遇到优先级小于当前运算符的元素为止。循环执行完后再将当前运算符压栈。另外须要注意的是，只有遇到右括号时，左括号才出栈
4) 当遇到右括号")"时，循环执行出栈操做并加入到list中，直到遇到左括号为止。并将左括号弹出，但不加入list中
5) 表达式的值读取完后，将操做符栈中的全部元素弹出并加入到list中
执行完上面步骤后，list中存储的顺序即为咱们转换后的后缀表达式的结果
转换实例
下面利用上面定义的转换规则，将表达式 1+((2+3)*4)-5 以图解的方式描述其转换过程
1.首先定义一个存储操做符的栈 Stack<String> stack = new Stack<>() ，和一个存储最终后缀表达式的列表 List<String> list = new ArrayList<>()
2.读取表达式，首先读取到数字 1 ，按照上述规则，直接添加至list中。此时stack和list结构以下
3.而后读取到操做符 + ，此时stack为空，按照上述规则，直接入栈，此时stack和list结构以下
4.接下来的两次读取都是左括号，按照咱们的规则，左括号直接入栈，此时stack和list结构以下
5.接着读取到数字2，按照咱们的规则，数字直接加入list中，此时stack和list结构以下
6.接着读取到操做符+，按照咱们的规则，此时栈不为空且栈顶元素为左括号，而只有遇到右括号时，左括号才出栈，因此+运算符直接入栈，此时stack和list结构以下
7. 接着读取到数字3，根据咱们的规则，数字直接加入list中，此时stack和list结构以下
8. 继续向后读取，读到到右括号 ")"，按照咱们的规则，执行stack出栈并加入list中操做，直到遇到左括号，并将左括号弹出，但不加入list中，此时stack和list结构以下
9.接着读取到操做符 * ，按照咱们的规则，此时栈顶元素为左括号，只需将操做符压栈便可，此时stack和list结构以下
10.接下来读取到数字4，按照规则直接将数字加入list中便可，此时stack和list结构以下
11.接下来读取到右括号")"，按照咱们的规则，执行stack出栈并加入list中操做，直到遇到左括号，并将左括号弹出，但不加入list中，此时stack和list结构以下
12.继续向后读取，此时读取到操做符-，按照咱们的规则，当栈不为空且当前优先级小于等于栈顶操做符优先级时，循环执行出栈并加入list操做。循环执行完再将当前操做符入栈
13.读取最后一个元素为数字5，按照规则，直接加入list中便可。当表达式读取完后，依此弹出操做符栈中的全部元素，并加入list中，此时stack和list结构以下
此时list中的顺序即为咱们转换后的后缀表达式的顺序，即：1 2 3 + 4 * + 5 -
转换代码
1 private static List<String> parseToSuffixExpression(List<String> expressionList) { 2 //建立一个栈用于保存操做符 3 Stack<String> opStack = new Stack<>(); 4 //建立一个list用于保存后缀表达式 5 List<String> suffixList = new ArrayList<>(); 6 for(String item : expressionList){ 7 //获得数或操做符 8 if(isOperator(item)){ 9 //是操做符 判断操做符栈是否为空 10 if(opStack.isEmpty() || "(".equals(opStack.peek()) || priority(item) > priority(opStack.peek())){ 11 //为空或者栈顶元素为左括号或者当前操做符大于栈顶操做符直接压栈 12 opStack.push(item); 13 }else { 14 //不然将栈中元素出栈如队，直到遇到大于当前操做符或者遇到左括号时 15 while (!opStack.isEmpty() && !"(".equals(opStack.peek())){ 16 if(priority(item) <= priority(opStack.peek())){ 17 suffixList.add(opStack.pop()); 18 } 19 } 20 //当前操做符压栈 21 opStack.push(item); 22 } 23 }else if(isNumber(item)){ 24 //是数字则直接入队 25 suffixList.add(item); 26 }else if("(".equals(item)){ 27 //是左括号，压栈 28 opStack.push(item); 29 }else if(")".equals(item)){ 30 //是右括号 ，将栈中元素弹出入队，直到遇到左括号，左括号出栈，但不入队 31 while (!opStack.isEmpty()){ 32 if("(".equals(opStack.peek())){ 33 opStack.pop(); 34 break; 35 }else { 36 suffixList.add(opStack.pop()); 37 } 38 } 39 }else { 40 throw new RuntimeException("有非法字符！"); 41 } 42 } 43 //循环完毕，若是操做符栈中元素不为空，将栈中元素出栈入队 44 while (!opStack.isEmpty()){ 45 suffixList.add(opStack.pop()); 46 } 47 return suffixList; 48 } 49 /** 50 * 判断字符串是否为操做符 51 * @param op 52 * @return 53 */ 54 public static boolean isOperator(String op){ 55 return op.equals("+") || op.equals("-") || op.equals("*") || op.equals("/"); 56 } 57 58 /** 59 * 判断是否为数字 60 * @param num 61 * @return 62 */ 63 public static boolean isNumber(String num){ 64 return num.matches("\\d+"); 65 } 66 67 /** 68 * 获取操做符的优先级 69 * @param op 70 * @return 71 */ 72 public static int priority(String op){ 73 if(op.equals("*") || op.equals("/")){ 74 return 1; 75 }else if(op.equals("+") || op.equals("-")){ 76 return 0; 77 } 78 return -1; 79 }
这里为了方便操做，将原中缀表达式字符串转换为list结构，转换list的代码以下
1 /** 2 * 将表达式转为list 3 * @param expression 4 * @return 5 */ 6 private static List<String> expressionToList(String expression) { 7 int index = 0; 8 List<String> list = new ArrayList<>(); 9 do{ 10 char ch = expression.charAt(index); 11 if(ch < 47 || ch > 58){ 12 //是操做符，直接添加至list中 13 index ++ ; 14 list.add(ch+""); 15 }else if(ch >= 47 && ch <= 58){ 16 //是数字,判断多位数的状况 17 String str = ""; 18 while (index < expression.length() && expression.charAt(index) >=47 && expression.charAt(index) <= 58){ 19 str += expression.charAt(index); 20 index ++; 21 } 22 list.add(str); 23 } 24 }while (index < expression.length()); 25 return list; 26 }
注：char类型本质为int类型，查看assic码表可知，0～9对应的char在 47~58之间，因此代码依此来判断是数字仍是操做符。另外代码中有判断多位数状况，请注意
下面展现测试代码
1 public static void main(String []args){ 2 3 String expression = "1+((2+3)*4)-5"; 4 List<String> expressionList = expressionToList(expression); 5 System.out.println("expressionList="+expressionList); 6 //将中缀表达式转换为后缀表达式 7 List<String> suffixList = parseToSuffixExpression(expressionList); 8 System.out.println(suffixList); 9 }
测试结果以下：
与咱们上述描述的结果相同，以上即为中缀表达式转换后缀表达式的过程及相关代码。另外附上根据后缀表达式求值的代码，感兴趣的能够参考
1 /** 2 * 根据后缀表达式list计算结果 3 * @param list 4 * @return 5 */ 6 private static int calculate(List<String> list) { 7 Stack<Integer> stack = new Stack<>(); 8 for(int i=0; i<list.size(); i++){ 9 String item = list.get(i); 10 if(item.matches("\\d+")){ 11 //是数字 12 stack.push(Integer.parseInt(item)); 13 }else { 14 //是操做符，取出栈顶两个元素 15 int num2 = stack.pop(); 16 int num1 = stack.pop(); 17 int res = 0; 18 if(item.equals("+")){ 19 res = num1 + num2; 20 }else if(item.equals("-")){ 21 res = num1 - num2; 22 }else if(item.equals("*")){ 23 res = num1 * num2; 24 }else if(item.equals("/")){ 25 res = num1 / num2; 26 }else { 27 throw new RuntimeException("运算符错误！"); 28 } 29 stack.push(res); 30 } 31 } 32 return stack.pop(); 33 }
测试运算代码以下
1 public static void main(String []args){ 2 3 String expression = "1+((2+3)*4)-5"; 4 List<String> expressionList = expressionToList(expression); 5 System.out.println("中缀表达式转为list结构="+expressionList); 6 //将中缀表达式转换为后缀表达式 7 List<String> suffixList = parseToSuffixExpression(expressionList); 8 System.out.println("对应的后缀表达式列表结构="+suffixList); 9 //根据后缀表达式计算结果 10 int calculateResult = calculate(suffixList); 11 System.out.printf(expression+"=%d\n",calculateResult); 12 }
计算结果以下
总结
中缀表达式转后缀表达式的难点在于转换规则，固然这个规则是研究算法的人已经帮咱们制定好的，咱们只须要按照这个规则实现代码便可。若是上述代码有问题可在留言区回复，谢谢