Java 实现《编译原理》中间代码生成 - 逆波兰式生成与计算 - 程序解析

落日映苍穹つ 2022-01-11 02:37 263阅读 0赞

### Java 实现《编译原理》中间代码生成 -逆波兰式生成与计算 - 程序解析 ###

编译原理学习笔记

#### （一）逆波兰式是什么？ ####

**逆波兰式**（Reverse Polish notation，RPN，或逆波兰记法），也叫 **后缀表达式**（将运算符写在操作数之后）

一般的表达式又称 **中缀表达式**，这种表达式的二元运算符放在两个运算量 **之间**。而逆波兰表达式又称 **后缀表达式**，这种表达式把运算符放在运算量 **后面**。

比如如 a+b 的逆波兰式表示为 ab+

> **注意：逆波兰式是一个无括号表达式；逆波兰式的运算符出现的顺序就是原表达式的运算顺序。**

#### （二）逆波兰式编译原理有什么关系？ ####

逆波兰式，三元式，四元式等是编译原理 - 中间代码生成阶段的常见的中间代码形式。

#### （三）本篇任务 ####

通过设计，使用 Java 语言编写一个逆波兰式生成程序，测试效果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9pY29kZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]

#### （四）Java 源代码 ####

package com.java997.analyzer.rpn;
    
    import java.util.HashMap;
    import java.util.Map;
    import java.util.Scanner;
    import java.util.Stack;
    
    /** * <p> * 逆波兰式 * * @author XiaoPengwei * @since 2019-06-19 */
    public class RpnMain { 
    
        /** * 检查算术表达术括号是否匹配, 语法是否正确 * * @param s 算术表达术 * @return boolean */
        public boolean isMatch(String s) { 
    
            //括号符号栈
            Stack<Character> charStack = new Stack<>();
    
            //将表达式的字符串转换成数组
            char[] charArray = s.toCharArray();
    
            //遍历数组
            for (char aChar : charArray) { 
                if (aChar == '(') { 
                    charStack.push(aChar);
                } else if (aChar == ')') { 
                    //如果是 ) , 且栈为空则返回 false
                    if (charStack.isEmpty()) { 
                        return false;
                    } else { 
                        //如果是 ) , 且栈不为空则返回 false
                        //peek() 是返回栈顶的值, 不做其他操作
                        if (charStack.peek() == '(') { 
                            //把栈顶的值删除
                            charStack.pop();
                        }
                    }
                }
            }
            //走到这里, 栈为空则表达式正确
            return charStack.empty();
        }
    
        /** * 判断是否为操作符 + - * / * * @param charAt * @return boolean */
        public boolean isOperator(char charAt) { 
            return charAt == '+' || charAt == '-' || charAt == '*' || charAt == '/';
        }
    
        /** * 根据正确的表达式, 获取逆波兰式 * * @param input * @return java.lang.String */
        public StringBuilder getRpn(String input) { 
            //结果
            StringBuilder sb = new StringBuilder();
            sb.append("The RPN is: ");
            //运算符栈
            Stack<Character> opStack = new Stack();
    
            //运算符优先级
            Map<Character, Integer> opMap = new HashMap(5);
            opMap.put('(', 0);
            opMap.put('+', 1);
            opMap.put('-', 1);
            opMap.put('*', 2);
            opMap.put('/', 2);
    
            //处理字符串
            for (int i = 0; i < input.length(); i++) { 
                //如果是'('直接压栈
                if (input.charAt(i) == '(') { 
                    opStack.push('(');
                } else if (new RpnMain().isOperator(input.charAt(i))) { 
                    //如果是运算符
                    char curOp = input.charAt(i);
                    //如果运算符栈是空，就直接压栈
                    if (opStack.isEmpty()) { 
                        opStack.push(curOp);
                    } else if (opMap.get(curOp) > opMap.get(opStack.peek())) { 
                        //运算符栈不为空，且当当前运算符的优先级比站内第一个运算符的优先级高的时候，压栈
                        opStack.push(curOp);
                    } else { 
                        //栈不为空，且运算符的优先级小于等于栈顶元素
                        for (int j = 0; j <= opStack.size(); j++) { 
                            //弹出栈内第一个元素
                            char ch = opStack.pop();
                            sb.append(ch);
                            if (opStack.isEmpty()) { 
                                opStack.push(curOp);
                                break;
                            } else if (opMap.get(curOp) > opMap.get(opStack.peek())) { 
                                opStack.push(curOp);
                                break;
                            }
                        }
                    }
                } else if (input.charAt(i) == ')') { 
                    //如果是')'就把站内'('上的元素都弹出栈
                    for (int j = 0; j < opStack.size(); j++) { 
                        char c = opStack.pop();
                        if (c == '(') { 
                            break;
                        } else { 
                            sb.append(c);
                        }
                    }
                } else if ('A'<=input.charAt(i)&&input.charAt(i)<='Z'){ 
                    //如果是字母就直接添加
                    sb.append(input.charAt(i));
                }else if ('a'<=input.charAt(i)&&input.charAt(i)<='z'){ 
                    //如果是字母就直接添加
                    sb.append(input.charAt(i));
                }else if (Character.isDigit(input.charAt(i))){ 
                    //如果是数字
                    sb.append(input.charAt(i));
                }else { 
                    return new StringBuilder("But the expression contains unrecognizable characters");
                }
            }
    
            //把栈内剩余的运算符都弹出站
            for (int i = 0; i <= opStack.size(); i++) { 
                sb.append(opStack.pop());
            }
    
            return sb;
        }
    
        public static void main(String[] args) { 
            RpnMain rpnMain = new RpnMain();
            Scanner sc = new Scanner(System.in);
    
            while (true) { 
                System.out.println("==========================\nPlease input an expression:");
                String input = sc.nextLine();
    
                if ("q".equals(input)) { 
                    sc.close();
                    return;
                } else { 
                    if (rpnMain.isMatch(input)) { 
                        System.out.println("The expression's brackets are matched");
                        // 获取逆波兰式
                        System.out.println(rpnMain.getRpn(input));
                    } else { 
                        System.out.println("Error: The expression's brackets are not matched! Enter 'q' to exit");
                    }
                }
            }
        }
    }

**测试：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9pY29kZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9pY29kZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]: /images/20220111/46fad176bd9348b799826a1c352d6e10.png