首页 > 代码库 > 堆栈的应用:四则表达式运算
堆栈的应用:四则表达式运算
堆栈的经典应用,四则表达式的元算。这里只能操作的符号是:+ - * / ()。不支持大括号...
下面是代码:
package net.itaem.test; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Stack; /** * 堆栈的应用 * 使用这个堆栈完成四则表达式的运算 四则:+ - * // * 比如:3 + (15-1)*2 -10 = 21 * */ public class StackApply { //四则表达式,也就是中缀表达式 private String source; //程序不验证输入的表达式是否合法,所以请保证输入的表达式有效,否则计算结果可能无效 //要求结果的四则表达式 public StackApply(String source){ if(source == null || "".equals(source)) throw new RuntimeException("输入的表达式不能为空"); this.source = source; } //将中缀表达式变成后缀表达式 public List<String> toLaterPattern(){ //定义一个堆栈,用来保存操作符号 Stack<Character> calStack = new Stack<Character>(); //定义一个顺序表,用来存储表达式中的数字 List<Integer> intList = new LinkedList<Integer>(); //后缀表达式的最后结果 List<String> resultList = new ArrayList<String>(); //取出中缀表达式里面的全部数字 String[] intArrays = source.split("[^0-9]"); //将数字添加到集合中,并且去掉空值 for(String intArray: intArrays){ if(!"".equals(intArray)){ intList.add(Integer.parseInt(intArray)); } } int index = 0; int fromIndex = 0; //遍历后缀表达式 for(int i=0; i<source.length();){ //如果是数字,将数字添加到后缀表达式中 if(isNumber(source.charAt(i))){ //添加数值到结果集 resultList.add(intList.get(index) + ""); //查看这个数值占用的位数 int intLength = (intList.get(index) + "").length(); //修改下一个i的值 i = source.indexOf(intList.get(index) + "", fromIndex) + intLength; //记录下下一个数值的起始处 fromIndex = i; index++; } //如果是 + - * / ( ) 这四个符号,进行进出站操作 else if(isCalculator(source.charAt(i))){ //如果是‘(‘,进入堆栈 if(source.charAt(i) == ‘(‘){ calStack.add(source.charAt(i)); //弹出第一栈顶到第一个(之间的操作符号 }else if(‘)‘ == source.charAt(i)){ //将数字的内容出栈 Character pop = null; //输出()之间的内容 while((pop = calStack.pop()) != ‘(‘){ char[] p = new char[1]; p[0] = pop; //将出栈的内容添加到结果集中 resultList.add(new String(p)); } }else{ //这里处理 + - * /的情况 //是* / if(source.charAt(i) == ‘*‘ || source.charAt(i) == ‘/‘){ calStack.push(source.charAt(i)); //因为 * /的优先级比较高,直接压入堆栈之中 }else if(source.charAt(i) == ‘+‘ || source.charAt(i) == ‘-‘){ //判断堆栈里面的内容,看看优先级关系 if(calStack.isEmpty()){ //如果为空,直接添加进去堆栈之中 calStack.push(source.charAt(i)); }else{ //取出第一个运算符号,这里不是弹出 char pop = calStack.peek(); //查看是否是优先级比较高的符号 if(pop == ‘*‘ || pop == ‘/‘){ while(!calStack.isEmpty()){ //输出所有优先级比较高的运算符 pop = calStack.pop(); if(pop == ‘*‘ || pop == ‘/‘){ //如果是 * /,优先级比较高,压入到堆栈中 resultList.add(pop + ""); }else{ //优先级比较低,停止 break; } } //弹出完成之后,要将此次的操作符添加到堆栈中 calStack.push(source.charAt(i)); }else{ //如果是相同优先级的+ -,添加到堆栈之中 // 1-2-3-4不满足结合律,所以要特殊处理,将数字改变为负数 if(source.charAt(i) == ‘-‘ && pop == ‘-‘){ resultList.set(index-1, -intList.get(index-1) + ""); } calStack.push(source.charAt(i)); } } } } i++; } } //将堆栈里面所有的操作符号取出来 List<String> pops = new LinkedList<String>(); while(!calStack.isEmpty()){ pops.add(calStack.pop()+""); } for(String pop: pops){ resultList.add(pop); } return resultList; } public String each(char c){ return null; } private boolean isCalculator(char c) { switch(c){ case ‘+‘: case ‘-‘: case ‘*‘: case ‘/‘: case ‘(‘: case ‘)‘:return true; default:return false; } } //判断一个字符是否是数字 private boolean isNumber(char c) { switch(c){ case ‘0‘: case ‘1‘: case ‘2‘: case ‘3‘: case ‘4‘: case ‘5‘: case ‘6‘: case ‘7‘: case ‘8‘: case ‘9‘:return true; default:return false; } } //返回计算结果 public float result(){ //得到后缀运算表达式的内容 List<String> laterPattern = toLaterPattern(); //用来保存计算结果的堆栈 Stack<Float> floatStack = new Stack<Float>(); float calResult = 0; //计算结果 //计算过程:如果是数字,进堆栈,如果是运算操作符,出栈,然后执行运算,再将运算结果压入堆栈 for(String c: laterPattern){ if(c.matches("-?\\d+")){ //将数字取出来,然后压入堆栈中 //将数字压入到堆栈中 floatStack.push(Float.parseFloat(c)); }else{ //取出两个操作数 float first = floatStack.pop(); float second = 0; //处理是负数的情况 if(!floatStack.isEmpty()){ second = floatStack.pop(); } char choose = c.toCharArray()[0]; switch(choose){ case ‘+‘: calResult = second+first; break; case ‘-‘: //2-(-2)==4,所以这里要特殊处理 if(first > 0){ calResult = second - first; }else{ calResult = second + first; } break; case ‘*‘: calResult = second*first; break; case ‘/‘: calResult = second/first; //记得转为float,避免出现 3/2 == 1的情况 break; default:throw new RuntimeException("操作符有错误...目前暂且不支持+ - * / ( ) 之外的运算符"); } //将计算结果压入堆栈 floatStack.push(calResult); } } //最后一个栈顶元素就是结果 return floatStack.pop(); } public static void main(String[] args) { System.out.println("1+2+3+4 = " + new StackApply("1+2+3+4").result()); System.out.println("1+2+3*4 = " + new StackApply("1+2+3*4").result()); System.out.println("(-11)+2+3*4 = " + new StackApply("(-11)+2+3*4").result()); System.out.println("11+2/3*4 = " + new StackApply("11+2/3*4").result()); System.out.println("1*2*3*4 = " + new StackApply("1*2*3*4").result()); System.out.println("1/(2/(3/4)) = 1/2/3/4 = " + new StackApply("1/2/3/4").result() + " = " + new StackApply("1/2/3/4").result()); //相当于是 1/(2/(3/4)) System.out.println("1+2*3-1 = " + new StackApply("1+2*3-1").result()); System.out.println("1-2-3-4 = " + new StackApply("1-2-3-4").result()); } }
上面的代码可能有点乱,不过主要的思想就是堆栈的应用
运算结果:
1+2+3+4 = 10.0 1+2+3*4 = 15.0 (-11)+2+3*4 = 3.0 11+2/3*4 = 11.166667 1*2*3*4 = 24.0 1/(2/(3/4)) = 1/2/3/4 = 0.375 = 0.375 1+2*3-1 = 5.0 1-2-3-4 = -8.0
总结:堆栈是一个FIRST IN LAST OUT,典型的FILO的数据结构。在计算机中,应用很广泛,大家可以认真研究下...
堆栈的应用:四则表达式运算
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。