java实现任意四则运算表达式求值算法
本文实例讲述了java实现任意四则运算表达式求值算法。分享给大家供大家参考。具体分析如下：
该程序用于计算任意四则运算表达式。如4*(10+2)+1的结果应该为49。
算法说明：
1.首先定义运算符优先级。我们用一个
Map<String,Map<String,String>>
来保存优先级表。这样我们就可以通过下面的方式来计算两个运算符的优先级了：
/**
*查表得到op1和op2的优先级
*@paramop1运算符1
*@paramop2运算符2
*@return">","<"或"="
*/
publicStringpriority(Stringop1,Stringop2){
returnpriorityMap.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中弹出２个操作数，从optStack中弹出1个运算符，并计算结果。
当optStrack栈为空时（即栈顶元素为'#'），numStack栈的栈顶元素即为表达式的值。
算法实现：
/**
*算术表达式求值。
*3+4*12结果为51
*@authorwhf
*
*/
publicclassEvaluateExpression{
//运算符优先级关系表
privateMap<String,Map<String,String>>priorityMap=newHashMap<String,Map<String,String>>();
privateLinkedStack<String>optStack=newLinkedStack<String>();
//运算符栈
privateLinkedStack<Double>numStack=newLinkedStack<Double>();
//操作数栈
/**
*计算表达式
*@paramexp四则运算表达式,每个符号必须以空格分隔
*@return
*/
publicdoublecalcualte(Stringexp){
StringTokenizerst=newStringTokenizer(exp);
while(st.hasMoreTokens()){
Stringtoken=st.nextToken();
process(token);
}
returnnumStack.pop();
}
/**
*读入一个符号串。
*如果是数字，则压入numStack
*如果是运算符，则将optStack栈顶元素与该运算符进行优先级比较
*如果栈顶元素优先级低，则将运算符压入optStack栈,如果相同，则弹出左括号，如果高，则取出２个数字，取出一个运算符执行计算，然后将结果压入numStack栈中
*@paramtoken
*/
privatevoidprocess(Stringtoken){
while(false=="#".equals(optStack.getTop())||false==token.equals("#")){
//tokenisnumeric
if(true==isNumber(token)){
numStack.push(Double.parseDouble(token));
break;
//tokenisoperator
}else{
Stringpriority=priority(optStack.getTop(),token);
if("<".equals(priority)){
optStack.push(token);
break;
}elseif("=".equals(priority)){
optStack.pop();
break;
}else{
doubleres=calculate(optStack.pop(),numStack.pop(),numStack.pop());
numStack.push(res);
}
}
}
}
/**
*执行四则运算
*@paramopt
*@paramn1
*@paramn2
*@return
*/
privatedoublecalculate(Stringopt,doublen1,doublen2){
if("+".equals(opt)){
returnn2+n1;
}elseif("-".equals(opt)){
returnn2-n1;
}elseif("*".equals(opt)){
returnn2*n1;
}elseif("/".equals(opt)){
returnn2/n1;
}else{
thrownewRuntimeException("unsupportedoperator:"+opt);
}
}
/**
*检查一个String是否为数字
*@paramtoken
*@return
*/
privatebooleanisNumber(Stringtoken){
intLEN=token.length();
for(intix=0;ix<LEN;++ix){
charch=token.charAt(ix);
//跳过小数点
if(ch=='.'){
continue;
}
if(false==isNumber(ch)){
returnfalse;
}
}
returntrue;
}
/**
*检查一个字符是否为数字
*@paramch
*@return
*/
privatebooleanisNumber(charch){
if(ch>='0'&&ch<='9'){
returntrue;
}
returnfalse;
}
/**
*查表得到op1和op2的优先级
*@paramop1运算符1
*@paramop2运算符2
*@return">","<"或"="
*/
publicStringpriority(Stringop1,Stringop2){
returnpriorityMap.get(op1).get(op2);
}
/**
*构造方法，初始化优先级表
*/
publicEvaluateExpression(){
//initializestack
optStack.push("#");
//initializeprioritytable
//+
Map<String,String>subMap=newHashMap<String,String>();
subMap.put("+",">");
subMap.put("-",">");
subMap.put("*","<");
subMap.put("/","<");
subMap.put("(","<");
subMap.put(")",">");
subMap.put("#",">");
priorityMap.put("+",subMap);
//-
subMap=newHashMap<String,String>();
subMap.put("+",">");
subMap.put("-",">");
subMap.put("*","<");
subMap.put("/","<");
subMap.put("(","<");
subMap.put(")",">");
subMap.put("#",">");
priorityMap.put("-",subMap);
//*
subMap=newHashMap<String,String>();
subMap.put("+",">");
subMap.put("-",">");
subMap.put("*",">");
subMap.put("/",">");
subMap.put("(","<");
subMap.put(")",">");
subMap.put("#",">");
priorityMap.put("*",subMap);
///
subMap=newHashMap<String,String>();
subMap.put("+",">");
subMap.put("-",">");
subMap.put("*",">");
subMap.put("/",">");
subMap.put("(","<");
subMap.put(")",">");
subMap.put("#",">");
priorityMap.put("/",subMap);
//(
subMap=newHashMap<String,String>();
subMap.put("+","<");
subMap.put("-","<");
subMap.put("*","<");
subMap.put("/","<");
subMap.put("(","<");
subMap.put(")","=");
//subMap.put("#",">");
priorityMap.put("(",subMap);
//)
subMap=newHashMap<String,String>();
subMap.put("+",">");
subMap.put("-",">");
subMap.put("*",">");
subMap.put("/",">");
//subMap.put("(","<");
subMap.put(")",">");
subMap.put("#",">");
priorityMap.put(")",subMap);
//#
subMap=newHashMap<String,String>();
subMap.put("+","<");
subMap.put("-","<");
subMap.put("*","<");
subMap.put("/","<");
subMap.put("(","<");
//subMap.put(")",">");
subMap.put("#","=");
priorityMap.put("#",subMap);
}
}
程序测试：
Stringexp="4*(10+2)+1#"; EvaluateExpressionee=newEvaluateExpression(); out.println(ee.calcualte(exp));
运行结果为49。
希望本文所述对大家的C++程序设计有所帮助。