使用到的栈结构:
import java.lang.reflect.Array; /** * 泛型栈 * * @param <T> */ public class Stack<T>{ private Class<T> type;// 栈元素所属的类 private int size;// 栈深度 private T[] arr;// 用数组存储 private int top;// 栈顶元素的下标 public Stack(Class<T> type,int size){ this.type = type; this.size=size; arr=createArray(size); top=-1; } /** * 创建数组 * @param size * @return */ @SuppressWarnings("unchecked") private T[] createArray(int size) { return (T[]) Array.newInstance(type, size); } /** * 压栈 * @param t */ public void push(T t){ top++; arr[top]=t; } /** * 出栈 * @return */ public T pop(){ T t=arr[top]; top--; return t; } /** * 取栈顶元素 * @return */ public T peek(){ return arr[top]; } /** * 判断栈是否为空 * @return */ public boolean isEmpty(){ return top==-1; } /** * 判断栈是否满了 * @return */ public boolean isFull(){ return top==(size-1); } /** * 展示栈内容 */ public void display(){ System.out.println("底Bottom"); for(int i=0;i<top+1;i++){ System.out.println(i+":"+arr[i]); } System.out.println("顶Top"); } public static void main(String[] args){ Stack<String> s=new Stack<String>(String.class,100); s.push("以恒心为良友"); s.push("以经验为参谋"); s.push("以小心为兄弟"); s.push("以希望为哨兵"); /*while(!s.isEmpty()){ String str=s.pop(); System.out.println(str); }*/ s.display(); } }
代码:
import java.util.ArrayList; import java.util.List; // 辅助类 class Item{ String value; boolean isNumber; public Item(String value,boolean isNumber){ this.value=value; this.isNumber=isNumber; } public Item(char c,boolean isNumber){ this.value=String.valueOf(c); this.isNumber=isNumber; } public String toString(){ return ""+value+" & "+isNumber; } } /** * 算术表达式求值 */ public class ArithCaculator{ private String line;// 输入的算式 private String result;// 计算得到的结果 public ArithCaculator(String line){ this.line=line; int length=line.length();
// 得到包含数字和操作符的列表 List<Item> ls=new ArrayList<Item>(); String str=""; for(int i=0;i<length;i++){ char ch=line.charAt(i); if((ch>='0' && ch<='9') || ch=='.'){ str+=ch; }else if(ch=='+' || ch=='-' || ch=='*' || ch=='/' || ch=='(' || ch==')' ){ if(str.length()>0){ ls.add(new Item(str,true)); str=""; } ls.add(new Item(ch,false)); } if(i==length-1 && str.length()>0){ ls.add(new Item(str,true)); } } // 得到后序表达式 ls=getPostfix(ls); // 计算后序表达式 this.result=getValue(ls); } // 对后序表达式进行计算 private String getValue(List<Item> ls){ Stack<Item> stack=new Stack<Item>(Item.class,ls.size()); double result; for(Item it:ls){ if(it.isNumber){ stack.push(it); }else{ // 栈先进后出所以颠倒 double op2=Double.parseDouble(stack.pop().value); double op1=Double.parseDouble(stack.pop().value); result=0; char ch=it.value.charAt(0); if(ch=='+'){ result=op1+op2; }else if(ch=='-'){ result=op1-op2; }else if(ch=='*'){ result=op1*op2; }else if(ch=='/'){ result=op1/op2; } stack.push(new Item(String.valueOf(result),true)); } } return stack.pop().value; } // 得到后序表达式 private List<Item> getPostfix(List<Item> ls){ List<Item> retval=new ArrayList<Item>(); Stack<Character> stack=new Stack<Character>(Character.class,ls.size()); for(Item it:ls){ if(it.isNumber){ retval.add(it); }else{ if("+".equals(it.value) || "-".equals(it.value) ){ gotOper(stack,retval,it.value,1); }else if("*".equals(it.value) || "/".equals(it.value) ){ gotOper(stack,retval,it.value,2); }else if("(".equals(it.value)){ stack.push('('); }else if(")".equals(it.value)){ gotParen(stack,retval,')'); } } } while(stack.isEmpty()==false){ retval.add(new Item(stack.pop(),false)); } return retval; } private void gotOper(Stack<Character> stack,List<Item> ls,String opThis,int prec){ while(stack.isEmpty()==false){ char opTop=stack.pop(); if(opTop=='('){ stack.push(opTop); break; }else{ int prec2=2; if(opTop=='+' || opTop=='-'){ prec2=1; } if(prec2<prec){ stack.push(opTop); break; }else{ ls.add(new Item(opTop,false)); } } } stack.push(opThis.charAt(0)); } private void gotParen(Stack<Character> stack,List<Item> ls,char ch){ while(stack.isEmpty()==false){ char chTop=stack.pop(); if(chTop=='('){ break; }else{ ls.add(new Item(chTop,false)); } } } public String getLine() { return line; } public String getResult() { return result; } public static void main(String[] args){ String[] arr=new String[]{"2+3+5","2+(3*5)-6","4+5*(1+2)","1*2+3*4","(3+4)*5/2+33","5+17+12.5","8.0/(3.0-(8.0/3.0))","((10.0*10.0)-4.0)/4.0"}; for(String str:arr){ ArithCaculator a=new ArithCaculator(str); System.out.println(a.getLine()+"="+a.getResult()); } } }
输出:
2+3+5=10.0 2+(3*5)-6=11.0 4+5*(1+2)=19.0 1*2+3*4=14.0 (3+4)*5/2+33=50.5 5+17+12.5=34.5 8.0/(3.0-(8.0/3.0))=23.99999999999999 ((10.0*10.0)-4.0)/4.0=24.0
本文转自张昺华-sky博客园博客,原文链接:http://www.cnblogs.com/xiandedanteng/p/3881557.html,如需转载请自行联系原作者