算术运算的设计
package come.feiqiang.stack;import java.util.Scanner;import java.util.Stack;import java.util.regex.Pattern;public class Algorithm {/** * 验证各种括号的匹配问题，是对栈的基本应用： * @param expression * @return */public static boolean isBalanced(String expression){final char LEFT_NOMAL='(';final char RIGHT_NOMAL=')';final char LEFT_CURLY='{';final char RIGHT_CURLY='}';final char LEFT_SQUARE='[';final char RIGHT_SQUARE=']';Stack<Character> store=new Stack<Character>();int i;boolean failed=false;for(i=0;!failed&&i<expression.length();i++){switch(expression.charAt(i)){case LEFT_NOMAL:case LEFT_CURLY:case LEFT_SQUARE:store.push(expression.charAt(i));break;case RIGHT_NOMAL:if(store.isEmpty()||store.pop()!=LEFT_NOMAL){failed=true;}break;case RIGHT_CURLY:if(store.isEmpty()||store.pop()!=LEFT_CURLY){failed=true;}break;case RIGHT_SQUARE:if(store.isEmpty()||store.pop()!=LEFT_SQUARE){failed=true;}break;}}return (store.isEmpty()&&!failed);}/** * 计算完全加括号的算术： * @param numbers 数字栈 * @param operations 操作符栈 * 算法： * do * if(下一个输入是数值) * 进数值栈else if(下一个输入是操作符) * 进操作符栈 * else if(下一个输入是右括号) * 弹出两个数值，弹出一个操作符，将后弹出的数值与前弹出的数值作运算，将操作结果压入数值栈 * 如果栈为空，或操作数为空，抛出异常 * else if(下一个输入是左括号) * 跳过 * else 抛出非法字符异常 *while(还有更多输入)* 算法缺点：没有检查括号的正确匹配情况，有兴趣的读者可以自己研究一下 **/public static void evaluateStackTops(Stack<Double> numbers, Stack<Character> operations){double operand1;double operand2;operand1=numbers.pop();operand2=numbers.pop();char operation=operations.pop();switch(operation){case '+':numbers.push(operand1+operand2);break;case '-':numbers.push(operand1-operand2);break;case '*':numbers.push(operand1*operand2);break;case '/':numbers.push(operand1/operand2);break;default:throw new IllegalArgumentException("Illegal Operation");}}public static double evaluate(String expression){Stack<Double> numbers=new Stack<Double>();Stack<Character> operations=new Stack<Character>();Scanner input=new Scanner(expression);String next;final Pattern CHARACTER=Pattern.compile("\\S.*?");final Pattern UNSIGN_DOUBLE=Pattern.compile("(((\\d+\\.?\\d*)|(\\.\\d+))([+-]?\\d+)?.*?)");while(input.hasNext()){if(input.hasNext(UNSIGN_DOUBLE)){next=input.findInLine(UNSIGN_DOUBLE);numbers.push(new Double(next));}else{next=input.findInLine(CHARACTER);switch(next.charAt(0)){case '+':case '-':case '*':case '/':operations.push(next.charAt(0));break;case ')':evaluateStackTops(numbers,operations);break;case '(':break;default:throw new IllegalArgumentException("Illegal character");}}}if(numbers.size()!=1){throw new IllegalArgumentException("Illegal input Exception");}return numbers.pop();}/** * 后缀表达式的计算： * @param expression * @return * 算法： * 初始化一个由双精度实数构成的栈 * while(表达式中有更多输入) * if(下一个输入是数值) * 读取下一个元素并压入栈中 * else * (下一个输入是操作符) * 弹出两个操作数，根据操作符运算后将结果压入栈中 * while end **/public static double evaluatePostfix(String expression){double answer;Scanner scanner=new Scanner(expression);Stack<Double> numbers=new Stack<Double>();Pattern UNSIGN_DOUBLE=Pattern.compile("((\\d+\\.?\\d*)|(\\.\\d+))([+-]?\\d+)?.*?");Pattern CHARACTER=Pattern.compile("\\S.*?");while(scanner.hasNext()){if(scanner.hasNext(UNSIGN_DOUBLE)){numbers.push(new Double(scanner.findInLine(UNSIGN_DOUBLE)));}else if(scanner.hasNext(CHARACTER)){double operand2=numbers.pop();double operand1=numbers.pop();switch(scanner.findInLine(CHARACTER).charAt(0)){case '+':numbers.push(operand1+operand2);break;case '-':numbers.push(operand1-operand2);break;case '*':numbers.push(operand1*operand2);break;case '/':numbers.push(operand1/operand2);break;default:throw new IllegalArgumentException("the expression is't right");}}else{throw new IllegalArgumentException("the expression is't right");}}if(numbers.size()!=1){throw new IllegalArgumentException("illegal expression");}answer=numbers.pop();return answer;}/** * 由普通的中缀表达是转化为后缀表达式： * @param expression * @return * 算法： * 略 */public static String convertMidToPost(String expression){String answer="";Stack<Character> operations=new Stack<Character>();Pattern UNSIGN_DOUBLE=Pattern.compile("((\\d+\\.?\\d*)|(\\.\\d+))([+-]?\\d+)?.*?");Pattern CHARACTER=Pattern.compile("\\S.*?");Scanner scanner=new Scanner(expression);while(scanner.hasNext()){if(scanner.hasNext(UNSIGN_DOUBLE)){answer+=scanner.findInLine(UNSIGN_DOUBLE)+" ";}else{char m;if(scanner.hasNext(CHARACTER)){switch((m=scanner.findInLine(CHARACTER).charAt(0))){case '+':case '-':case '*':case '/':case '(':operations.push(m);break;case ')':char c=operations.pop();if((operations.isEmpty())||(c!='+'&&c!='-'&&c!='*'&&c!='/')){throw new IllegalArgumentException("not valid expression");}answer+=String.valueOf(c)+" ";if(operations.pop()!='('){throw new IllegalArgumentException("not valid expression");}break;default:throw new IllegalArgumentException("not valid expression");}}}}return answer;}/** * 带有优先级的中缀表达式的求解 * @param expression * @return * 算法： * 初始化一个空字符串和一个字符栈 * while(表达式还有更多输入) * if(下一个输入为数值) * 读取下一个输入，并入字符串尾部 * else *if(下一个输入是优先级较高的（*,/）运算符||当前栈为空||当前栈顶元素为'(') * 读取字符下一个输入符号 *else if(下一个输入是'(') * 读取字符并且压入栈中 *else if(下一个输入是')') * 将当前栈中元素全部加入字符串尾部 *else if(下一个输入是运算符) * 将栈中的符号弹出，并入字符串尾部 * 读取下一个字符串，并且压入栈中 *else * 弹出非法表达是一茶馆 * while end ** 下面的代码与算法稍有差别，因为算法是后写的，所以算法的入错能力更强 */public static String priorityOfMid(String expression){String answer="";Scanner scanner=new Scanner(expression);Pattern UNSIGN_DOUBLE=Pattern.compile("((\\d+\\.?\\d*)|(\\.\\d+))([+-]?\\d+)?.*?");Pattern CHARACTER=Pattern.compile("\\S.*?");Stack<Character> operations=new Stack<Character>();if(!scanner.hasNext()){throw new IllegalArgumentException("illegal exception");}while(scanner.hasNext()){if(scanner.hasNext(UNSIGN_DOUBLE)){answer+=scanner.findInLine(UNSIGN_DOUBLE)+" ";}else{char occurrence=scanner.findInLine(CHARACTER).charAt(0);if((operations.isEmpty()||operations.peek()=='(')||(occurrence=='*'||occurrence=='/')&&(operations.peek()=='+'||operations.peek()=='-')){System.out.println("in 1");operations.push(occurrence);}else if(occurrence=='('){operations.push(occurrence);System.out.println("in 2");}else if(occurrence==')'){System.out.println("in 3");while(!operations.isEmpty()&&operations.peek()!='('){answer+=String.valueOf(operations.pop())+" ";}if(operations.pop()!='('){throw new IllegalArgumentException("illegal exception");}}else{System.out.println("in 4");answer+=operations.pop()+" ";operations.push(occurrence);}}}while(!operations.isEmpty()){answer+=operations.pop()+" ";}scanner.close();return answer;}public static void main(String args[]){//System.out.println(evaluate("(((2+3)+3)*3)"));//System.out.println("concequence:"+evaluatePostfix("2 3.0*5-6/"));String midExpression="2";String postExpression=priorityOfMid(midExpression);System.out.println("postExpression:"+postExpression);System.out.print(midExpression+"=");double x=evaluatePostfix(postExpression);System.out.println(x);}}
页:
[1]