使用栈实现中缀表达式转后缀表达式

我就是我 2023-02-12 05:39 53阅读 0赞

# 例子 #

例题1  
中缀表达式“8+4-6\*2”  
后缀表达式表示为：8 4 + 6 2 \* -

例题2  
中缀表达式：（70 + 30） \*20 + 10 / 2 - 3  
后缀表达式： 70 30 + 20 \* 10 2 / + 3 -

例题3  
中缀表达式： 10 \* 3 +（3-1）\* 2 - 10 / 2  
后缀表达式：10 3 \* 3 1 - 2 \* + 10 2 / -

例题3：  
中缀表达式“2\*(3+5)+7/1-4  
后缀表达式表示为：3 5 + 2 \* 7 1 /4 - +

例题4：  
中缀表达式为：1.0+(2-3)*4+4/2  
后缀表达式为：1.0 2 3 - 4* \+ 4 2 / +

# 题目解析 #

容易错  
小心空格  
小心数字不一定只有一位  
注意数字的反转问题

*  初始化两个栈：运算符栈S1和储存中间结果的栈S2；
 *  从左至右扫描中缀表达式；
    
     *  遇到操作数时，将其压入S2；
     *  遇到运算符时，比较其与S1栈顶运算符的优先级：
        
         *  如果S1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
         *  否则，若优先级比栈顶运算符的高，也将运算符压入S1（注意转换为前缀表达式时是优先级较高或相同，而这里则不包括相同的情况）；
         *  否则，将S1栈顶的运算符弹出并压入到S2中，再次转到(4-1)与S1中新的栈顶运算符相比较；
     *  遇到括号时：
        
         *  如果是左括号“(”，则直接压入S1；
         *  如果是右括号“)”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到左括号为止，此时将这一对括号丢弃；
 *  循环扫描，直到表达式的最右边；
 *  将S1中剩余的运算符依次弹出并压入S2；
 *  依次弹出S2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式（转换为前缀表达式时不用逆序）。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]

[CC][]

## 第一版 ##

public class EcmDef {
        
        public static boolean isNumeric(String str) {
        
            String bigStr;
            try {
        
                bigStr = new BigDecimal(str).toString();
            } catch (Exception e) {
        
                return false;//异常 说明包含非数字。
            }
            return true;
        }
    
        // 数字越大优先级越高
        // 只有(，), +, -, * ,/ 六种符号。 置于 (和)不考虑
        public static int Priority(String oper){
        
            if (oper.equals("+") || oper.equals("-")){
        
                return 1;
            }else if (oper.equals("*") || oper.equals("/")){
        
                return 2;
            }else{
        
                throw  new RuntimeException("错误的符号:" + oper);
            }
        }
    
        //正整数
        public static String mu_back(String str) {
        
            Stack<String> numStack = new Stack<>();
            Stack<String> operStack = new Stack<>();
    
            int i = 0;
    
            while (true){
        
                if (i >= str.length()){
        
                    break;
                }
    
                char c = str.charAt(i);
                if (c == ' '){
        
                    i++; // 跳过
                    continue;  //进入下一轮循环
                }
    
                String s = String.valueOf(c);
    
                if (isNumeric(s)){
        
                    StringBuilder t = new StringBuilder();
                    t.append(s);
    
                    while (++i < str.length()){
        
                        s = String.valueOf(str.charAt(i));
                        if (isNumeric(s)){
        
                            t.append(s);
                        }else{
          // 不是数字就跳出循环
                            break;
                        }
                    }
    
                    // 指针反转
                    numStack.push(t.reverse().toString());
                    continue;
                }
    
    
                if (operStack.empty() || c ==   '('){
        
                    operStack.push(s);  // 入栈
                    i++;  // 指针前移
                }else if (c == ')'){
        
                   if (operStack.size() < 2){
        
                       throw new RuntimeException("表达式错误");
                   }
                   numStack.push(operStack.pop());
                   operStack.pop(); // 下一个一定是)。  )不用压栈
                   i++; // 指针前移
                }else{
        
                    if (operStack.size() < 1){
        
                        throw new RuntimeException("表达式错误");
                    }
    
                    if (operStack.peek().equals("(")){
         // 栈顶是(
                        operStack.push(s); //压栈
                        i++; // 指针前移
                        continue;
                    }
    
                    if (Priority(s) > Priority(operStack.peek())){
        
                        operStack.push(s);
                        i++;
                    }else{
        
                        numStack.push(operStack.pop());  // 优先级小于等于
                    }
                }
            }
    
            // 将符号栈导入数字栈
            while (!operStack.empty()){
        
                numStack.push(operStack.pop());
            }
    
            StringBuilder ans = new StringBuilder();
            while (!numStack.empty()){
        
                ans.append(numStack.pop());
                ans.append(" ");
            }
    
    
            return ans.reverse().toString();
        }
    
    
        public static void main(String[] args) {
        
            System.out.println(mu_back("10 * 3 +(3-1)* 2 - 10 / 2")); // 20 30 * 4 + 5 *
        }
    }

## 第二版 ##

https://www.runoob.com/java/data-intopost.html

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200526124351536.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[CC]: https://blog.csdn.net/antineutrino/article/details/6763722/