数据结构之中缀表达式转后缀表达式（Java实现）

上一篇文章中用java实现了后缀表达式的计算，链接https://blog.csdn.net/xindanding/article/details/90443998

但是我们在计算时不可能手动将要计算的表达式转为后缀再丢给计算器吧，这样的话那还要计算器干嘛，是吧。。。。

接下来要讲的是如何将中缀表达式转为后缀表达式。

首先，建立一个节点：  

//节点用于保存运算符，这与后缀表达式的计算不同

public class SignNode { String signName; SignNode next; public String getSignName() { return signName; } public void setSignName(String signName) { this.signName = signName; } public SignNode getNext() { return next; } public void setNext(SignNode next) { this.next = next; } }

其次，我们创建一个管理运算符的链表

//主要用于控制运算符的进出栈

public class SignList { private SignNode list; private int length; public SignNode element(){ return list; } public SignNode pop(){ SignNode signNode = new SignNode(); signNode = list; list = list.next; length --; return signNode; } public void push(SignNode signNode){ signNode.next = list; list = signNode; length ++; } public SignNode getList() { return list; } public void setList(SignNode list) { this.list = list; } public int getLength() { return length; } public void setLength(int length) { this.length = length; } }

接下来就是真正的操作和测试了

public class Main { private static Map<String, Integer> signMap = new HashMap<String, Integer>(); //存储运算符和优先级 private static String signCol = "+-*/()"; static { signMap.put("+", 1); signMap.put("-", 1); signMap.put("*", 4); signMap.put("/", 4); signMap.put("(", 0); //用于括号里不只一次运算时 比如（3*2-3） } public static void main(String[] args) { infix2suffix(); } private static void infix2suffix(){ // String str = "9,+,(,3,-,1,),*,3,+,10,/,2"; String str = "9,+,(,3,*,2,-,3,),*,3,+,10,/,2"; SignList signList = new SignList(); String[] exp = str.split(","); List<String> result = new ArrayList<String>(); for(int i = 0; i < exp.length; i++){ if(signCol.contains(exp[i])){ if("(".equals(exp[i])){ //如果是（ 入栈 SignNode node = new SignNode(); node.setSignName(exp[i]); signList.push(node); }else if(")".equals(exp[i])){ popStack(signList, result); } else { pushOrPopStack(signList, exp[i], result); } }else{ //不是运算符则添加到结果集 result.add(exp[i]); } } while(signList.getLength() > 0){ SignNode node = signList.pop(); result.add(node.getSignName()); } System.out.println(result); } private static void popStack(SignList signList, List<String> result){ SignNode node = signList.pop(); //将栈顶元素出栈 if(!"(".equals(node.getSignName())){ //如果栈顶元素不是左括号（ 添加到结果集 result.add(node.getSignName()); popStack(signList, result); //继续判断新的栈顶元素 } } private static void pushOrPopStack(SignList signList, String val, List<String> result){ if(signList.getLength() != 0) { //如果不为空栈 SignNode stackTop = signList.element(); //获取栈顶元素 if (signMap.get(stackTop.getSignName()) < signMap.get(val)) { //优先级高于栈顶元素，则入栈 SignNode signNode = new SignNode(); signNode.setSignName(val); signList.push(signNode); }else{ //否则 栈顶元素出栈 SignNode node = signList.pop(); result.add(node.getSignName()); //将栈顶元素的值加入到结果集 pushOrPopStack(signList, val, result); //继续与新的栈顶元素进行比较 } }else{ //如果为空栈 直接入栈 SignNode node = new SignNode(); node.setSignName(val); signList.push(node); } }

结果：[9, 3, 2, *, 3, -, 3, *, +, 10, 2, /, +]

如果有未考虑到的，希望大家指正