java實(shí)現(xiàn)任意四則運(yùn)算表達(dá)式求值算法
更新時(shí)間：2015年04月20日 15:03:30 作者：司青
這篇文章主要介紹了java實(shí)現(xiàn)任意四則運(yùn)算表達(dá)式求值算法,實(shí)例分析了基于java實(shí)現(xiàn)表達(dá)式四則運(yùn)算求值的原理與技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下
本文實(shí)例講述了java實(shí)現(xiàn)任意四則運(yùn)算表達(dá)式求值算法。分享給大家供大家參考。具體分析如下：
該程序用于計(jì)算任意四則運(yùn)算表達(dá)式。如 4 * ( 10 + 2 ) + 1 的結(jié)果應(yīng)該為 49。
算法說明：
1. 首先定義運(yùn)算符優(yōu)先級(jí)。我們用一個(gè)
Map<String, Map<String, String>>
來保存優(yōu)先級(jí)表。這樣我們就可以通過下面的方式來計(jì)算兩個(gè)運(yùn)算符的優(yōu)先級(jí)了：
/**
* 查表得到op1和op2的優(yōu)先級(jí)
* @param op1 運(yùn)算符1
* @param op2 運(yùn)算符2
* @return ">", "<" 或 "="
*/
public String priority(String op1, String op2) {
return priorityMap.get(op1).get(op2);
}
2. 掃描表達(dá)式字符串，每次讀入一個(gè) token 進(jìn)行處理。
使用兩個(gè)輔助棧：optStack用于保存運(yùn)算符，numStack用于保存操作數(shù). 我們用 '#' 作為表達(dá)式的起始和結(jié)果標(biāo)志符。
讀入一個(gè)token，如果它是數(shù)字，則壓入numStack棧中；
如果它是運(yùn)算符，則取出optStack棧的棧頂元素A，將 A 與 token 進(jìn)行優(yōu)先級(jí)比較。
如果 A < token，則將 token 壓入optStack棧。
如果 A = token，則說明 token和A是一對(duì)括號(hào)，此時(shí)將optStack棧的棧頂元素彈出。
如果 A > token，則從numStack中彈出２個(gè)操作數(shù)，從optStack中彈出1個(gè)運(yùn)算符，并計(jì)算結(jié)果。
當(dāng)optStrack棧為空時(shí)（即棧頂元素為 '#'），numStack棧的棧頂元素即為表達(dá)式的值。
算法實(shí)現(xiàn)：
/**
* 算術(shù)表達(dá)式求值。
* 3 + 4 * 12 結(jié)果為51
* @author whf
*
*/
public class EvaluateExpression {
// 運(yùn)算符優(yōu)先級(jí)關(guān)系表
private Map<String, Map<String, String>> priorityMap = new HashMap<String, Map<String, String>>();
private LinkedStack<String> optStack = new LinkedStack<String>();
// 運(yùn)算符棧
private LinkedStack<Double> numStack = new LinkedStack<Double>();
// 操作數(shù)棧
/**
* 計(jì)算表達(dá)式
* @param exp 四則運(yùn)算表達(dá)式, 每個(gè)符號(hào)必須以空格分隔
* @return
*/
public double calcualte(String exp) {
StringTokenizer st = new StringTokenizer(exp);
while (st.hasMoreTokens()) {
String token = st.nextToken();
process(token);
}
return numStack.pop();
}
/**
* 讀入一個(gè)符號(hào)串。
* 如果是數(shù)字，則壓入numStack
* 如果是運(yùn)算符，則將optStack棧頂元素與該運(yùn)算符進(jìn)行優(yōu)先級(jí)比較
* 如果棧頂元素優(yōu)先級(jí)低，則將運(yùn)算符壓入optStack棧,如果相同，則彈出左括號(hào)，如果高，則取出２個(gè)數(shù)字，取出一個(gè)運(yùn)算符執(zhí)行計(jì)算，然后將結(jié)果壓入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);
}
}
}
}
/**
* 執(zhí)行四則運(yùn)算
* @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);
}
}
/**
* 檢查一個(gè)String是否為數(shù)字
* @param token
* @return
*/
private boolean isNumber(String token) {
int LEN = token.length();
for (int ix = 0 ; ix < LEN ; ++ix) {
char ch = token.charAt(ix);
// 跳過小數(shù)點(diǎn)
if (ch == '.') {
continue;
}
if (false == isNumber(ch)) {
return false;
}
}
return true;
}
/**
* 檢查一個(gè)字符是否為數(shù)字
* @param ch
* @return
*/
private boolean isNumber(char ch) {
if (ch >= '0' && ch <= '9') {
return true;
}
return false;
}
/**
* 查表得到op1和op2的優(yōu)先級(jí)
* @param op1 運(yùn)算符1
* @param op2 運(yùn)算符2
* @return ">", "<" 或 "="
*/
public String priority(String op1, String op2) {
return priorityMap.get(op1).get(op2);
}
/**
* 構(gòu)造方法，初始化優(yōu)先級(jí)表
*/
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);
}
}
程序測(cè)試：
String exp = "4 * ( 10 + 2 ) + 1 #"; EvaluateExpression ee = new EvaluateExpression(); out.println(ee.calcualte(exp));
運(yùn)行結(jié)果為 49。
希望本文所述對(duì)大家的C++程序設(shè)計(jì)有所幫助。
您可能感興趣的文章:
- java數(shù)據(jù)結(jié)構(gòu)與算法之中綴表達(dá)式轉(zhuǎn)為后綴表達(dá)式的方法
- java實(shí)現(xiàn)中綴表達(dá)式轉(zhuǎn)后綴的方法
- Java正則表達(dá)式處理特殊字符轉(zhuǎn)義的方法
- Java后綴數(shù)組之求sa數(shù)組的實(shí)例代碼
- JAXB命名空間及前綴_動(dòng)力節(jié)點(diǎn)Java學(xué)院整理
- 關(guān)于各種排列組合java算法實(shí)現(xiàn)方法
- java字符串相似度算法
- java異或加密算法
- Java實(shí)現(xiàn)幾種常見排序算法代碼
- Java中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式實(shí)現(xiàn)方法詳解
相關(guān)文章
本文主要介紹了基于C++17實(shí)現(xiàn)的手寫線程池,自己實(shí)現(xiàn)了Any類,Semaphore類以及Result類的開發(fā),文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2024-08-08
這篇文章主要給大家介紹了關(guān)于C++中std::ifstream使用方法的相關(guān)資料,std::ifstream 是輸入文件流類,用于從文件中讀取數(shù)據(jù),文中通過代碼介紹的非常詳細(xì),需要的朋友可以參考下2024-06-06
由于函數(shù)調(diào)用可以使用函數(shù)名、函數(shù)指針、函數(shù)對(duì)象或有名稱的lambda表達(dá)式，可調(diào)用類型太豐富導(dǎo)致模板的效率極低。包裝器用于解決效率低的問題2022-08-08
使用C++實(shí)現(xiàn)鏈表元素的反轉(zhuǎn)
反轉(zhuǎn)鏈表是鏈表操作中一個(gè)經(jīng)典的問題,也是面試中常見的考題,本文將從思路到實(shí)現(xiàn)一步步地講解如何實(shí)現(xiàn)鏈表的反轉(zhuǎn),幫助初學(xué)者理解這一操作,我們將使用C++代碼演示具體實(shí)現(xiàn),同時(shí)分析時(shí)間復(fù)雜度和空間復(fù)雜度,需要的朋友可以參考下2025-02-02
該模塊基于pthread實(shí)現(xiàn)，sylar說，由于c++11中的thread也是由pthread封裝實(shí)現(xiàn)的，并且沒有提供讀寫互斥量，讀寫鎖，自旋鎖等，所以自己封裝了pthread，本文主要詳細(xì)介紹了C++高性能服務(wù)器框架中的線程模塊,需要的朋友可以參考下2023-06-06
本文主要介紹了C++訪問者模式模板函數(shù)無法重載的問題解決，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-12-12
C++中的模版總體可以分為兩大類：模版函數(shù)、模版類。本篇文章先寫模版函數(shù),需要的朋友可以參考下2017-02-02
VC中CWinThread類以及和createthread API的區(qū)別分析
這篇文章主要介紹了VC中CWinThread類以及和createthread API的區(qū)別分析,較為詳細(xì)的講述了CWinThread類的原理,并以實(shí)例形式對(duì)AfxBeginThread函數(shù)的內(nèi)部實(shí)現(xiàn)進(jìn)行了解釋說明,需要的朋友可以參考下2014-10-10
C++實(shí)現(xiàn)LeetCode(168.求Excel表列名稱)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(168.求Excel表列名稱),本篇文章通過簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-08-08
C語(yǔ)言中自動(dòng)隱式轉(zhuǎn)換與類型強(qiáng)制轉(zhuǎn)換實(shí)例分析
這篇文章主要介紹了C語(yǔ)言中自動(dòng)隱式轉(zhuǎn)換與類型強(qiáng)制轉(zhuǎn)換實(shí)例分析,需要的朋友可以參考下2014-07-07