java完成隨意率性四則運算表達式求值算法。本站提示廣大學習愛好者:(java完成隨意率性四則運算表達式求值算法)文章只能為提供參考,不一定能成為您想要的結果。以下是java完成隨意率性四則運算表達式求值算法正文
本文實例講述了java完成隨意率性四則運算表達式求值算法。分享給年夜家供年夜家參考。詳細剖析以下:
該法式用於盤算隨意率性四則運算表達式。如 4 * ( 10 + 2 ) + 1 的成果應當為 49。
算法解釋:
1. 起首界說運算符優先級。我們用一個
Map<String, Map<String, String>>
來保留優先級表。如許我們便可以經由過程上面的方法來盤算兩個運算符的優先級了:
/** * 查表獲得op1和op2的優先級 * @param op1 運算符1 * @param op2 運算符2 * @return ">", "<" 或 "=" */ public String priority(String op1, String op2) { return priorityMap.get(op1).get(op2); }
2. 掃描表達式字符串,每次讀入一個 token 停止處置。
應用兩個幫助棧:optStack用於保留運算符,numStack用於保留操作數. 我們用 '#' 作為表達式的肇端和成果標記符。
讀入一個token,假如它是數字,則壓入numStack棧中;
假如它是運算符,則掏出optStack棧的棧頂元素A,將 A 與 token 停止優先級比擬。
假如 A < token,則將 token 壓入optStack棧。
假如 A = token,則解釋 token和A是一對括號,此時將optStack棧的棧頂元素彈出。
假如 A > token,則從numStack中彈出2個操作數,從optStack中彈出1個運算符,並盤算成果。
當optStrack棧為空時(即棧頂元素為 '#'),numStack棧的棧頂元素即為表達式的值。
算法完成:
/** * 算術表達式求值。 * 3 + 4 * 12 成果為51 * @author whf * */ public class EvaluateExpression { // 運算符優先級關系表 private Map<String, Map<String, String>> priorityMap = new HashMap<String, Map<String, String>>(); private LinkedStack<String> optStack = new LinkedStack<String>(); // 運算符棧 private LinkedStack<Double> numStack = new LinkedStack<Double>(); // 操作數棧 /** * 盤算表達式 * @param exp 四則運算表達式, 每一個符號必需以空格分隔 * @return */ public double calcualte(String exp) { StringTokenizer st = new StringTokenizer(exp); while (st.hasMoreTokens()) { String token = st.nextToken(); process(token); } return numStack.pop(); } /** * 讀入一個符號串。 * 假如是數字,則壓入numStack * 假如是運算符,則將optStack棧頂元素與該運算符停止優先級比擬 * 假如棧頂元素優先級低,則將運算符壓入optStack棧,假如雷同,則彈出左括號,假如高,則掏出2個數字,掏出一個運算符履行盤算,然後將成果壓入numStack棧中 * @param token */ private void process(String token) { while (false == "#".equals(optStack.getTop()) || false == token.equals("#")) { // token is numeric if (true == isNumber(token)) { numStack.push(Double.parseDouble(token)); break; // token is operator } else { String priority = priority(optStack.getTop(), token); if ("<".equals(priority)) { optStack.push(token); break; } else if ("=".equals(priority)) { optStack.pop(); break; } else { double res = calculate(optStack.pop(), numStack.pop(), numStack.pop()); numStack.push(res); } } } } /** * 履行四則運算 * @param opt * @param n1 * @param n2 * @return */ private double calculate(String opt, double n1, double n2) { if ("+".equals(opt)) { return n2 + n1; } else if ("-".equals(opt)) { return n2 - n1; } else if ("*".equals(opt)) { return n2 * n1; } else if ("/".equals(opt)) { return n2 / n1; } else { throw new RuntimeException("unsupported operator:" + opt); } } /** * 檢討一個String能否為數字 * @param token * @return */ private boolean isNumber(String token) { int LEN = token.length(); for (int ix = 0 ; ix < LEN ; ++ix) { char ch = token.charAt(ix); // 跳太小數點 if (ch == '.') { continue; } if (false == isNumber(ch)) { return false; } } return true; } /** * 檢討一個字符能否為數字 * @param ch * @return */ private boolean isNumber(char ch) { if (ch >= '0' && ch <= '9') { return true; } return false; } /** * 查表獲得op1和op2的優先級 * @param op1 運算符1 * @param op2 運算符2 * @return ">", "<" 或 "=" */ public String priority(String op1, String op2) { return priorityMap.get(op1).get(op2); } /** * 結構辦法,初始化優先級表 */ public EvaluateExpression() { // initialize stack optStack.push("#"); // initialize priority table // + Map<String, String> subMap = new HashMap<String, String>(); subMap.put("+", ">"); subMap.put("-", ">"); subMap.put("*", "<"); subMap.put("/", "<"); subMap.put("(", "<"); subMap.put(")", ">"); subMap.put("#", ">"); priorityMap.put("+", subMap); // - subMap = new HashMap<String, String>(); subMap.put("+", ">"); subMap.put("-", ">"); subMap.put("*", "<"); subMap.put("/", "<"); subMap.put("(", "<"); subMap.put(")", ">"); subMap.put("#", ">"); priorityMap.put("-", subMap); // * subMap = new HashMap<String, String>(); subMap.put("+", ">"); subMap.put("-", ">"); subMap.put("*", ">"); subMap.put("/", ">"); subMap.put("(", "<"); subMap.put(")", ">"); subMap.put("#", ">"); priorityMap.put("*", subMap); // / subMap = new HashMap<String, String>(); subMap.put("+", ">"); subMap.put("-", ">"); subMap.put("*", ">"); subMap.put("/", ">"); subMap.put("(", "<"); subMap.put(")", ">"); subMap.put("#", ">"); priorityMap.put("/", subMap); // ( subMap = new HashMap<String, String>(); subMap.put("+", "<"); subMap.put("-", "<"); subMap.put("*", "<"); subMap.put("/", "<"); subMap.put("(", "<"); subMap.put(")", "="); //subMap.put("#", ">"); priorityMap.put("(", subMap); // ) subMap = new HashMap<String, String>(); subMap.put("+", ">"); subMap.put("-", ">"); subMap.put("*", ">"); subMap.put("/", ">"); //subMap.put("(", "<"); subMap.put(")", ">"); subMap.put("#", ">"); priorityMap.put(")", subMap); // # subMap = new HashMap<String, String>(); subMap.put("+", "<"); subMap.put("-", "<"); subMap.put("*", "<"); subMap.put("/", "<"); subMap.put("(", "<"); //subMap.put(")", ">"); subMap.put("#", "="); priorityMap.put("#", subMap); } }
法式測試:
String exp = "4 * ( 10 + 2 ) + 1 #"; EvaluateExpression ee = new EvaluateExpression(); out.println(ee.calcualte(exp));
運轉成果為 49。
願望本文所述對年夜家的C++法式設計有所贊助。