引例：某表达式的前缀形式为"+ -*^ABCD/E/F+GH",那么它的中缀形式为？
前缀表达式的操作前缀表达式是一种没有括号的算术表达式，就是前序表达式，不同于中缀表达式，它把运算符写在前面，操作数写在后面，前缀表达式也称为“波兰式”。例如，- 1 + 2 3，它等价于1-(2+3)。后缀表达式和前缀表达式十分相似，只是后缀表达式从左往右读入计算机。
前缀表达式：从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 op 次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果。
计算过程：题目中前缀形式为：±*^ABCD/E/F+GH
首先扫描 H,是数字 入栈 ，栈中为: H2)扫描 G 为数字 入栈 ,栈中为:G,H
3)扫描+ 为运算符 ,依次弹出G ,H ,得到 G+H 的结果 入栈，栈中为： G+H(在这里方便讲解 标记为 G+H)
4)扫描 F 为数字 ,入栈 ，栈中为 F, G+H
5)扫描 / 为运算符, 依次弹出 F,G+H ，计算F/(G+H) 的结果入栈 ，栈中为 F/(G+H)
6)扫描 E 为数字,入栈，栈中为 E, F/(G+H)
7)扫描 / 为运算符, 依次弹出E, F/(G+H) ，计算 E/(F/(G+H))
8)扫描 D 为数字,入栈 栈中为:D, E/(F/(G+H))
9)扫描 C 为数字,入栈 栈中为:C,D, E/(F/(G+H))
10)扫描 B 为数字,入栈 栈中为:B,C,D, E/(F/(G+H))
11)扫描 A 为数字,入栈 栈中为:A,B,C,D, E/(F/(G+H))
12)扫描^ 为运算符,依次弹出 A,B 计算 A^B的结果入栈, 栈中为：A^B ,C,D, E/(F/(G+H))
13)扫描为运算符,依次弹出 A^B,C 计算 A^BC的结果入栈, 栈中为：A^B* C,D, E/(F/(G+H))
14)扫描-为运算符,依次弹出 A^BC,D 计算 A^BC-D的结果入栈, 栈中为：A^B* C-D, E/(F/(G+H))
15)扫描+为运算符,依次弹出 A^BC-D, E/(F/(G+H)) 计算 A^BC-D+ E/(F/(G+H)) 的到结果
最后得到的表达式为： A^B* C-D+ E/(F/(G+H)) 代码实现中缀2前缀
中缀表达式转前缀表达式，利用前缀表达式求结果。
import java.util.ArrayList;import java.util.Collections;import java.util.List;/** * @Auther: 我爱双面奶 * @Date: 2018/7/18 22:53 * @Description: 中缀(infix)表达式转波兰式(polish notation)(前缀表达式) * */public class InfixToPNCalculate { public static void main(String[] args) { String str = "1+(6/2)-8*2+(20-4)"; List<String> pnStack = infixToPn(str); int result = getResrult(pnStack); System.out.println("结果："+result); } /** * 中缀转前缀表达式算法 * * 1、初始化两个栈：运算符栈opStack和存储前缀表达式栈pnStack； * 2、【反转】字符串，【从左至右】扫描中缀表达式； * 3、遇到操作数时，直接将其压入tempStack中； * 4、遇到运算符时，比较其与opStack栈顶运算符的优先级： * 4.1、如果opStack为空，或者栈顶运算符为右括号’)’，则直接将此运算符压入opStack中； * 4.2、否则，若优先级比栈顶运算符的优先级高或相等，则直接将此运算符压入opStack中； * 4.3、否则，将opStack栈顶的运算符弹出并压入到tempStack中，再次转入步骤4，与opStack中新的栈顶运算符相比较； * 5、遇到括号时： * 5.1、如果是右括号’)’，则直接压入opStack中； * 5.2、如果是左括号’(‘，则依次弹出opStack栈顶的运算符并压入tempStack中，知道遇到右括号’)’为止，此时将这一对括号丢弃； * 6、重复步骤2~5，直到表达式的最左边； * 7、将opStack中剩余的运算符依次弹出并压入tempStack中； * 8、依次弹出tempStack中的元素保存到result中，result即为中缀表达式转换所得的前缀表达式。 * @param strExpression 前缀表达式 * @return 后缀表达式 */ public static List<String> infixToPn(String strExpression){ StringBuilder stringBuilder = new StringBuilder(strExpression.trim());//将String对象转换为StringBuilder对象，为了转字符串 System.out.println("中缀表达式："+stringBuilder); stringBuilder = stringBuilder.reverse();//反转字符串 List<String> pnStack = new ArrayList();//前缀表达式栈 List<String> opStack = new ArrayList();//运算符栈 String falg = ""; char[] str = stringBuilder.toString().toCharArray(); //从左往右扫描 for(int i=0;i<str.length;i++ ){ if(isDigit((falg+str[i]).trim())){//判断flag+当前字符是否为数字 falg = (falg+str[i]).trim(); if(i==str.length-1){//当当前字符是数字，并且是最后一个字符时直接存入前缀表达式栈 //由于之前反转了，现在要反转回来，比如45在之前被反转为了54，需要反转回来 pnStack.add(new StringBuilder(falg).reverse().toString()); } }else {//当当前字符不是数字时 if(falg.trim()!=""&&isDigit((falg).trim())){//将上一次的flag存入前缀表达式栈 pnStack.add(new StringBuilder(falg).reverse().toString()); falg=""; } if(opStack.size()==0||opStack.get(opStack.size()-1).equals(")")){//对应4.1 opStack.add(String.valueOf(str[i])); }else if(str[i]==')'){//对应5.1 opStack.add(String.valueOf(str[i])); }else if(str[i]=='('){//对应5.2 while (opStack.size()!=0){ if(opStack.get(opStack.size()-1).equals(")")){ opStack.remove(opStack.size()-1); break; } pnStack.add(opStack.get(opStack.size()-1)); opStack.remove(opStack.size()-1); } }else if (str[i]=='*'||str[i]=='/'){//对应4.2 opStack.add(String.valueOf(str[i])); }else if(opStack.get(opStack.size()-1).equals("*")||opStack.get(opStack.size()-1).equals("/")){//对应4.3 pnStack.add(opStack.get(opStack.size()-1)); opStack.remove(opStack.size()-1); i--; }else {//对应4.2 opStack.add(String.valueOf(str[i])); } } } //对应7 while (opStack.size()!=0){ pnStack.add(opStack.get(opStack.size()-1)); opStack.remove(opStack.size()-1); } //反转List对象 Collections.reverse(pnStack); System.out.print("波兰式(前缀表达式)："); pnStack.stream().forEach(x-> System.out.print(x+" "));//迭代输出 System.out.println(""); return pnStack; } /** * 通过前缀表达式计算结果 * 1、借助中间结果栈tempStack，【从右至左】扫描表达式 * 2、遇到操作数时，将操作数入tempStack栈 * 3、遇到操作符时，从tempStack栈中弹出两个操作数，进行运行，然后将运算结果压入tempStack栈。 * 4、重复1~3，直到pnStack为空 * 5、tempStack栈剩下的最后一个元素即所求结果 * @param pnStack 中间结果栈 * @return */ public static int getResrult(List<String> pnStack){ int result = 0; List<String> tempResultStack = new ArrayList<>(); while (pnStack.size()!=0){ int end = pnStack.size()-1; int resultend = tempResultStack.size()-1; if(isDigit(pnStack.get(end))){//对应2 tempResultStack.add(pnStack.get(end)); pnStack.remove(end); }else {//对应3 if(pnStack.get(end).equals("*")) { result = Integer.parseInt(tempResultStack.get(resultend)) * Integer.parseInt(tempResultStack.get((resultend - 1))); }else if (pnStack.get(end).equals("/")){ result = Integer.parseInt(tempResultStack.get(resultend)) / Integer.parseInt(tempResultStack.get((resultend - 1))); }else if (pnStack.get(end).equals("+")){ result = Integer.parseInt(tempResultStack.get(resultend)) + Integer.parseInt(tempResultStack.get((resultend - 1))); }else if (pnStack.get(end).equals("-")){ result = Integer.parseInt(tempResultStack.get(resultend)) - Integer.parseInt(tempResultStack.get((resultend - 1))); } pnStack.remove(end); tempResultStack.remove(resultend); tempResultStack.remove(resultend-1); tempResultStack.add(String.valueOf(result)); } } // System.out.println(tempResultStack.toString()); return result; } /** * 判断一个字符串是否为数值 * @param str 判断的字符串 * @return 返回一个boolean值 */ public static boolean isDigit(String str){ return str.matches("[0-9]{1,}"); }} 附录1.代码参考作者：我爱双面奶
https://note.youdao.com/ynoteshare1/index.html?id=ffe93536b1140b00bbe205282990e1ff&type=note
2.题目来自牛客网