咸鱼学数据结构与算法中缀表达式转前缀表达式
目录
咸鱼学数据结构与算法——中缀表达式转前缀表达式
目录
一、中缀表达式转前缀表达式算法介绍
(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;
}
}