首页 > 代码库 > 数据结构之中序遍历转兴许遍历(JAVA实现)(二)
数据结构之中序遍历转兴许遍历(JAVA实现)(二)
算法流程:
主要分为四步:
1.当前字符为数字或者字母,则直接输出
2.当前字符为)。则在栈中匹配输出。一直匹配到),则停止输出(就是将)及其顶上的元素所有弹出来输出)
3.当前字符为操作符。则比較当前字符的入栈优先级(icp)和字符栈内优先级(isp)。假设icp<=isp,则将栈内操作符弹出输出,然后反复3
4.当前字符为空,则将栈中元素依次弹出输出
百度百科上面的描写叙述:
1、建立运算符栈stackOperator用于运算符的存储。压入‘\0‘。
2、预处理表达式,正、负号前加0(假设一个加号(减号)出如今最前面或左括号后面,则该加号(减号)为正负号) 。
3、顺序扫描表达式。假设当前字符是数字(优先级为0的符号),则直接输出该数字。假设当前字符为运算符或括号(优先级不为0的符号)。则推断第4点 。
4、若当前运算符为‘(‘,直接入栈;若为‘)‘,出栈并顺序输出运算符直到遇到第一个‘(‘。遇到的第一个‘(‘出栈但不输出;若为四则运算符,比較栈顶元素与当前元素的优先级:假设 栈顶元素运算符优先级 >= 当前元素的优先级,出栈并顺序输出运算符直到 栈顶元素优先级 < 当前元素优先级。然后当前元素入栈;假设 栈顶元素 < 当前元素,直接入栈。
5、反复第3点直到表达式扫描完成。
6、顺序出栈并输出运算符直到栈顶元素为‘\0‘。
当然我自己理解的就是依照自己实现的简单变化,没有包含大括号
我的代码:
// 中序遍历改为兴许遍历 public String tranform(String obj) { Stack<Character> stack = new Stack<Character>(); String obj2 = ""; for (int i = 0; i < obj.length(); i++) { char ch = obj.charAt(i); if (Character.isLetter(ch))// 字母或数字直接输出 { obj2 += ch; System.out.println(ch); } else if (ch == ')')// 在栈中一致匹配到)操作符才停止出栈 { char temp; while ((temp = stack.pop()) != '(') { obj2 += temp; System.out.println(temp); } } else // 比較操作符的进栈优先级 { if(stack.isEmpty()) { stack.push(ch); continue; } char temp = stack.peek(); while (icp(ch) <= isp(temp))//进栈优先级小于栈内优先级,则一直出栈 { System.out.println(temp); obj2+=temp; stack.pop(); if(stack.isEmpty())break; temp=stack.peek(); } stack.push(ch); } } //将栈中剩余的元素弹出来 while(!stack.isEmpty()) { char temp=stack.pop(); obj2+=temp; System.out.println(temp); } return obj2; } // 操作符在栈内的优先级 private int isp(char ch) { switch (ch) { case '+': case '-': return 2; case '*': case '/': return 4; case ')': return 7; case '(': return 1; default: break; } return 0; } // 操作符进栈的优先级优先级 private static int icp(char ch) { switch (ch) { case '+': case '-': return 3; case '*': case '/': return 5; case ')': return 1; case '(': return 7; default: break; } return 0; } public static void main(String[] args) { String objString="a*(b+c)+c/d"; TreeNode<Character> treeNode=new TreeNode<Character>(null); treeNode.tranform(objString); }执行效果:
a*(b+c)+c/d -》 abc+*cd/*
数据结构之中序遍历转兴许遍历(JAVA实现)(二)