中缀表达式转后缀表达式,Java实现
中缀转后缀是如何转换的网上已经讲解的很详细了,本文不做赘述。 如果不理解的同学可以看:https://www.bilibili.com/video/av18586085/?p=20 代码实现: public class Main { public static void main(String[] args) { Stack<String> stack = new Stack<>(); // new一个栈 String[] array = "2 * ( 9 + 6 / 3 - 5 ) + 4".split(" "); // 中缀表达式 List<String> list = new LinkedList<>(); // list存储后缀表达式 for (String s : array) { if (isNumber(s)) { // 数字直接输出 list.add(s); } else { // 1.根据当前读到的运算符判断是否需要弹出 // 1.1 如果栈当前不为空且s不是"("且栈顶不是"(",则判断运算符 // 反之:栈为空栈或当前字符为"("或栈顶是"(",则s直接入栈 if (stack.size() > 0 && !"(".equals(s) && !"(".equals(stack.peek())) { // 如果是")",将栈顶至第一个"("弹出 String top = null; if (")".equals(s)) { while (!"(".equals(top = stack.pop())) { list.add(top); } } else { // 如果是运算符,比较优先级,将优先级大于等于当前s的都弹出 while (stack.size() > 0 && compare(top = stack.peek(),s) > -1) { list.add(top); stack.pop(); } } } // 2.把当前运算符压入栈 if (!")".equals(s)) { stack.push(s); } } } // 3.最后栈中剩的一定是最后一个运算符和比最后一个运算符优先级小的运算符,否则之前就已经弹出了 while (stack.size() > 0) { list.add(stack.pop()); } // 4.输出后缀表达式 for (String s : list) { System.out.print(" " + s); } System.out.println(); } // 比较两个运算符,返回正数则a优先级大于b,负数则a优先级小于b private static int compare(String a,String b) { // "("的优先级比任何运算符都小 if ("(".equals(a)) { return -99999; } if ("(".equals(b)) { return 99999; // 本实现中b不会出现这种情况 } int aScore = "+".equals(a) || "-".equals(a) ? 0 : 1; int bScore = "+".equals(b) || "-".equals(b) ? 0 : 1; return aScore - bScore; } // 是数字则返回true private static isNumber(String s){ return "0123456789".contains(s); } } 说一下我自己的一点理解:
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |