栈的应用

约定不等于承诺〃 2021-09-26 07:28 342阅读 0赞

# 中缀表达式转换未后缀表达式： #

思路：  
1.从左至右扫描中缀表达式  
2.遇到数字时，则加入后缀表达式  
3.遇到运算符时：  
a) 若为‘（’, 直接入栈；  
b)若为‘）’，则依次将栈中的运算符加入到后缀表达式，直到出现‘（’，然后从栈中删除‘（’；  
c)若为出除括号以外的运算符，则1）当其优先级高于除‘（’以外的栈顶元素时，直接入栈，否则2）从栈顶元素开始，依次弹出比当前处理的运算符优先级高或等于的运算符，直到一个比它优先级低或者遇到第一个左括号为止。然后入栈。  
d)扫描到中缀表达式结束（‘\#’）时，将栈中的元素依次出栈（除了‘\#’）  
Java 代码：

package 表达式转换;
    
    import java.util.HashMap;
    import java.util.Map;
    import java.util.Scanner;
    import java.util.Stack;
    
    ///
    ///中缀表达式转换未后缀表达式
    ///
    public class MidToAfter {
    
        //操作符
        static Character[] ops={
       '#','(',')','+','-','*','/'};
    
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            //输入的表达式后面加上‘#’表示结束
            Scanner scanner=new Scanner(System.in);
            String s=scanner.nextLine();
            System.out.println(MidToAfter(s));
        }
    
        private static String MidToAfter(String s) {
            String result = "";
            // 建立栈内栈外操作符优先级
            // in stack priority 栈内优先级
            Map<Character, Integer> isp = new HashMap<Character, Integer>();
            isp.put('#', 0);
            isp.put('(', 1);
            isp.put('*', 5);
            isp.put('/', 5);
            isp.put('+', 3);
            isp.put('-', 3);
            isp.put(')', 6);
    
            //开始计算
            //建栈
            Stack<Character> stack=new Stack<>();
            stack.push('#');
            char[] ch=s.toCharArray();
            for(int i=0;i<ch.length;i++){
                //如果为操作符
                if(IsOp(ch[i])){
                    if(ch[i]=='#'){
                        while(!stack.isEmpty()&&!stack.peek().equals('#')){
                            result+=stack.pop();
                        }
                        return result;
                    }
                    //比较栈内外优先级
                    if(ch[i]=='(')
                        stack.push(ch[i]);
                    else if(ch[i]==')'){
                        while(!stack.isEmpty()&&!stack.peek().equals('(')){
                            result+=stack.pop();
                        }
                        stack.pop();
                    }else{
                        if(!stack.isEmpty()&&!stack.peek().equals('(')&&isp.get(stack.peek())< isp.get(ch[i])){
                            stack.push(ch[i]);
                        }
                        else{
                            while(!stack.isEmpty()&&!stack.peek().equals('#')&&(!stack.peek().equals('(')&&isp.get(stack.peek())>= isp.get(ch[i]))){
                                result+=stack.pop();
                            }
                            stack.push(ch[i]);
                        }
    
                    }
                }else{
                    //为操作数直接输出
                    result+=ch[i];
                }
            }
            return result;
        }
    
        //判断是操作符还是操作数
        private static boolean IsOp(char c){
            for(int i=0;i<ops.length;i++){
                if(ops[i]==c)
                    return true;
            }
            return false;
        }
    }

运行截图：  
![这里写图片描述][SouthEast]

[SouthEast]: /images/20210923/ea35fed364c24d42a4768e1ded05a773.png