爪哇国新游记之二十三"/>
爪哇国新游记之二十三
使用到的栈结构:
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博客园博客,原文链接:.html,如需转载请自行联系原作者
更多推荐
爪哇国新游记之二十三
发布评论