目录
一、中缀表达式转前缀表达式算法介绍
二、中缀表达式转前缀表达式代码实现
一、中缀表达式转前缀表达式算法介绍 (1) 初始化两个栈：运算符栈S1和储存中间结果的栈S2；(2) 从右至左扫描中缀表达式；(3) 遇到操作数时，将其压入S2；(4) 遇到运算符时，比较其与S1栈顶运算符的优先级： (4-1) 如果S1为空，或栈顶运算符为右括号“)”，则直接将此运算符入栈； (4-2) 否则，若优先级比栈顶运算符的较高或相等，也将运算符压入S1； (4-3) 否则，将S1栈顶的运算符弹出并压入到S2中，再次转到(4-1)与S1中新的栈顶运算符相比较；(5) 遇到括号时： (5-1) 如果是右括号“)”，则直接压入S1； (5-2) 如果是左括号“(”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号为止，此时将这一对括号丢弃；(6) 重复步骤(2)至(5)，直到表达式的最左边；(7) 将S1中剩余的运算符依次弹出并压入S2；(8) 依次弹出S2中的元素并输出，结果即为中缀表达式对应的前缀表达式。 二、中缀表达式转前缀表达式代码实现 //infixExperssion为中缀表达式public static List<String> InfixToPrefix(String infixExperssion){// 从右向左扫描 int index=infixExperssion.length()-1;// 用来存放前缀表达式 List<String> resultList=new ArrayList<String>();// 用来存放运算符 Stack<String> operStack=new Stack<String>();// 用来拼接数字，多位数字 String joint=""; while (true){// 当扫描完毕后，退出循环 if(index<0){ break; }// 如果扫描到是操作数，直接将结果加入到结果list中// 如果是多位数的问题已经解决 if (isNum(infixExperssion.charAt(index))){// 由于是从右向左扫描，所以拼接要从右侧开始拼接 joint=infixExperssion.charAt(index)+joint;// 判断是否越界，如果越界则不需要比较 if(index>1){// 判断下一个字符是否为数字 if(!isNum(infixExperssion.charAt(index-1))){ resultList.add(joint); joint="";// 执行完成后让index加一，不然会陷入死循环 index--; }else { index--; }// 已经是最后一位数了，不需要看下一位了 }else { resultList.add(joint); joint=""; index--; }// 如果是运算符，根据运算符优先级判断运算符是否进入运算符栈 }else if(isOper(infixExperssion.charAt(index))){ char oper=infixExperssion.charAt(index);// 如果为空，则直接加入到运算符中 if (operStack.empty()){ operStack.push(String.valueOf(oper)); index--;// 如果优先级大于运算符栈顶运算符的优先级，将运算符加入到运算符栈中 }else if(Priority(oper)>Priority(operStack.peek().charAt(0))){ operStack.push(String.valueOf(oper)); index--;// 将运算符栈栈顶的运算符加入到List数组中 }else { resultList.add(operStack.pop());// index++; }// 如果是右括号，将右括号放入运算符栈中 }else if(infixExperssion.charAt(index)==')'){ operStack.push(String.valueOf(infixExperssion.charAt(index))); index--;// 根据右括号来去除左括号 } else if(infixExperssion.charAt(index)=='('){ while (!operStack.empty()&&!operStack.peek().equals(")")){ resultList.add(operStack.pop()); }// 丢弃右括号 operStack.pop(); index--; } }// 将运算符栈中的运算符弹到list中 while (!operStack.empty()){ resultList.add(operStack.pop()); }// 将结果反转 Collections.reverse(resultList); return resultList; }//比较优先级 public static int Priority(char ch){ if (ch=='+'||ch=='-'){ return 1; }else if (ch=='*'||ch=='/'){ return 2; }else { return 0; } } //判断是否为运算符 public static boolean isOper(char oper){ if(oper=='+'||oper=='-'||oper=='*'||oper=='/'){ return true; }else { return false; } }//判断是否为数字 public static boolean isNum(char num){ if(num>=48&&num<=57){ return true; }else { return false; } }