突然之间心血来潮,就是想试一试数据结构怎么用.到现在才感觉的,数据结构是一种思想,一种思维方式,用怎样的方式去解决怎样的问题,这些是数据结构和算法给我们的.
言归正传吧,说说这个小计算器(其实还有太多需要扩展和改进的地方).暂时只局限在加减乘除,因为定义的是int类型的,所以也限制在整数运算吧.
主要思路是这样的:计算器最主要的部分是获取用户输入,然后根据算法将获取到的输入存储成为hashu.html" target="_blank">二叉树.当然,肯定要用栈存储的.
先看一下简单的分析:
1+2-3:? 存储成二叉树应该是这样的:节点上的值为运算符,左右孩子为数值:
???? +
??? /?? \
? +??? 3
/??? \
1??? 2??
也就是说,存好后用后序方法来进行读取,然后计算.
如果有*和/,则如下:
1+2*3-6/2:
?????????????????? -
?????????????? /??? ?\
?????????????+?? ??? /
????????????/??\??? / \
???????????1?? *? 6? 2
??????????????? /?\
???????????????2? 3???
其实,从这些分析上,可以得出一个结论,暂且是对于这个计算器范围内的结论(没有括号之类的...)
(1)两个栈,一个CTack,用来存放暂时的caozuofu.html" target="_blank">操作符,一个TTack,用来存放二叉树.两个栈结构,一个栈存放的是String类型,另一个存放二叉树Node类型.
(2)一次对用户输入的字符进行遍历,通过下面的原则判断是否压栈还是出栈组成二叉树.
?? 方式:首先,在输入字符是数字时,先创建一个TTack,左右孩子赋值为null,data值赋值为数字.
????????? 输入遍历到操作符时:a: CTack为空;b:CTack当前操作符优先级<读入的操作符 ; 压栈CTack
????????????????????????????????????? aa:CTack当前操作符优先级>=读入操作符优先级,新建Node,出栈TTack中的两个Node分别
??????????????????????????????????????????? 作为新Node的左右孩子,操作符作为节点值,之后再次压栈TTack.
(3)读完后,如果CTack还不是null,则以此取出TTack中的两个Node作为新Node的左右孩子,CTack出栈的操作符作为节点值.之后压栈.
?
思路大体就是这样,这个过程中其实有很多问题,其中比较难的是:如果操作符和已经有的是相等的关系,那么就是循环进行新建节点,压栈这些操作.
?
核心程序:
package com.pipi.MainProcess; import com.pipi.structure.Node; import com.pipi.structure.OperatorStacks; import com.pipi.structure.Stacks; import com.pipi.util.CheckPriority; import com.pipi.util.Operate; public class Structure { OperatorStacks CTack = new OperatorStacks(); //存放符号 Stacks TTack = new Stacks(); //存放二叉树结构 private StringBuffer dowithstr = new StringBuffer(); public String DowithStr(String getStr){ char[] cc = getStr.toCharArray(); String ch = new String(); for (int i = 0;i < cc.length; i++){ if(!Operate.isOperate(String.valueOf(cc[i]))){//如果是数字 ch = ch + String.valueOf(cc[i]); int j = (i+1) == cc.length?(cc.length-1):i+1; if(Operate.isOperate(String.valueOf(cc[j])) || cc.length == i+1){ Node n = new Node(); n.setData(ch); n.setLchild(null); n.setRchild(null); TTack.push(n); ch = ""; } }else{ // 如果栈里面当前操作符优先级小于或者等于ch优先级,则压栈ch while(CheckPriority.getPriority(CTack.getFirstStr()) >= CheckPriority.getPriority(String.valueOf(cc[i]))){// 如果栈里面当前操作符优先级大于ch优先级,则栈里面当前操作符出栈,并取得TTack中两个操作数进行运算 Node a = TTack.pop();//第一个出栈 Node b = TTack.pop();//第二个出栈 Node n = new Node(); n.setData(CTack.pop()); n.setLchild(b); n.setRchild(a); TTack.push(n); // int m = CTack.getPoint()>0?(CTack.getPoint()-1):0; // CTack.setPoint(m); } CTack.push(String.valueOf(cc[i])); } } while(CTack.getPoint() > 0){ Node a = TTack.pop();//第一个出栈 Node b = TTack.pop();//第二个出栈 Node n = new Node(); n.setData(CTack.pop()); n.setLchild(b); n.setRchild(a); TTack.push(n); } //计算最后的值 int result = Operate.getResult(TTack.pop()); /** * 遍历二叉树元素,得出结果后没有用啦 */ int j = TTack.getPoint(); //当前栈中的个数 for(int i = 0; i < j; i++){ Node n = TTack.pop(); System.out.println(n.getData()+"--------from the getData()."); System.out.println(n.getLchild()+"--------from getLchild()."); System.out.println(n.getRchild()+"--------from getRchild()."); } /** * 遍历操作符,最后没有了 */ int k = CTack.getPoint(); for(int i = 0; i < k; i++){ System.out.println(CTack.pop()); } // return ""; return result+""; } }
?
对栈的操作:
package com.pipi.structure; public class OperatorStacks { private int point = 0; //当前位置 private String[] sb = new String[100]; //当前位置的内容 /** * 获取最上面的元素 * 如果有,则返回,如果没有,则返回一个"###" */ public String getFirstStr(){ if(point>0){ return sb[point-1]; } return "###"; } public String pop(){ if(point > 0){ point = point - 1; } return sb[point]; } public void push(String n){ sb[point] = n; point++; } public int getPoint() { return point; } public void setPoint(int point) { this.point = point; } public String[] getSb() { return sb; } public void setSb(String[] sb) { this.sb = sb; } }
?
工具操作:其中getResult方法用到了递归调用的方法.
package com.pipi.util; import com.pipi.structure.Node; import com.pipi.structure.OperatorStacks; import com.pipi.structure.Stacks; /** * 两个数之间的计算 * @author ya皮皮 * */ public class Operate { public static String opr(String str, int num2, int num1){ if(str.equals("+")){ return (num2 + num1 +""); }else if(str.equals("-")){ return (num2-num1 +""); }else if(str.equals("*")){ return (num2*num1 +""); }else{ if(num1!=0) { return (num2/num1 +""); } return 0+""; } } /** * * @param TTack * @param CTack * @return */ //计算 public static int getResult(Node n){ String result = new String(); if(null == n.getLchild() && null == n.getRchild()){ result = n.getData(); }else{ result = opr(n.getData(),getResult(n.getLchild()),getResult(n.getRchild())); } return Integer.parseInt(result); } /** * 判断是不是操作符 */ public static boolean isOperate(String str){ return "+-*/".indexOf(str) != -1?true:false; } }
?定义优先级:
public class CheckPriority { public static int getPriority(String s){ if(null == s){ return 0; } if(s.equals("*") || s.equals("/")){ //* / 是1级 return 2; }else if(s.equals("+") || s.equals("-")){ // + -是0级 return 1; }else{ return -1; } } }
?
定义二叉树:
?
package com.pipi.structure; /** * * @author pipi * 定义二叉树 */ public class Node { String data = new String(); //数据 Node lchild = null; //左孩子,如果没有,设置为null Node rchild = null; //右孩子,如果没有,设置为null public String getData() { return data; } public void setData(String data) { this.data = data; } public Node getLchild() { return lchild; } public void setLchild(Node lchild) { this.lchild = lchild; } public Node getRchild() { return rchild; } public void setRchild(Node rchild) { this.rchild = rchild; } }
?
总结:
其实,这个程序只是实现了一个思想,还有很多没有考虑到的地方,还有很多代码需要重构.总的来说,学会了这种思想也是一个小小的进步,接下来会好好完善一下代码.
GOGO~
?