java中栈的应用-带括号的算术表达式

2018-02-05 11:06:01来源:oschina作者:天佑我儿人点击

分享

问题分析:


表达式有中缀表达式,后缀表达式和前缀表达式;


其中中缀表达式就是我们平常写的算术表达式,而后缀表达式就是将运算符放在两个操作数之后,前缀则放在之前;


例如:中缀表达式:A+(B-C/D)*E 对应的后缀表达式就是 ABCD/-E*+,前缀类比


由于后缀表达式中无运算优先级又无括号的约束问题,因此计算一个后缀表达式比计算一个中缀表达式咬简单




1将原算术表达式转换成后缀表达式



要使运算符出现的次序与真正的算术顺序一致,就要使优先数高的以及括号内的运算符先出现在前,所以需要一个栈来保留未被送到后缀表达式的运算符



算法思路如下:


(1)初始化一个运算符栈


(2)从算术表达式输入的字符串中从左到右读取一个字符


(3)若字符使操作数,则直接送往后缀表达式


(4)若当前字符是左括号,则压进栈内


(5)若当前字符为运算符,则进行下面操作:


(5.1)当运算符为空时,则将其压入栈中


(5.2)当此运算符优先级高于栈顶字符,则将其压入栈中;否则,去出栈中字符送到后缀表达式,并将当前运算符压栈


(6)若当前字符为右括号,则反复将栈顶弹出送往后缀表达式,直到栈顶为左括号为止,再将左括号丢弃


(7)若读取还未完毕,则转到步骤2


(8)若读取结束,则将栈中的运算符弹出并送往后缀表达式











2计算后缀表达式



问题分析:


要计算后缀表达式的值比较简单,只要先找到运算符,在去找之前最后两个操作数;


利用一个栈来保留后缀表达式中还未参加运算的操作数,称为操作数栈




算法分析如下:


1.初始化一个操作数栈



2从左到右依次读入后缀表达式的字符



(1)若当前为操作数,则将操作数压入栈中



(2)若当前为运算符,则从栈顶弹出两个操作数参与运算,并将运算结果压入操作栈中



3重复步骤2直到后缀表达式为空为止,则操作栈中的栈顶元素即为后缀表达式的计算结果


import java.util.Stack;
public class Example3_3 {
//将算术表达式转换为后缀表达式的函数,结果一字符串的形式返回
public String converToPostfix(String expression)throws Exception{
Stack st=new Stack<>(); //初始化一个运算符栈
String postfix=new String(); //用于储存后缀表达式
for(int i=0;expression!=null&&i char c=expression.charAt(i);
if(' '!=c){
//为左括号
if(isOpenParent(c)){
st.push(c);
}//为右括号
else if(isCloseParent(c)){
char ac=st.pop();
while(!isOpenParent(ac)){
postfix=postfix.concat(String.valueOf(ac));
ac=st.pop();
}
}//为运算符
elseif(isOperator(c)){
//运算栈非空,取出栈顶优先级高的运算符送完后缀表达式
if(!st.empty()){
char ac=st.pop();
//栈取出的字符优先级比c高
while(!st.isEmpty()&&priority(ac)>=priority(c)){
postfix=postfix.concat(String.valueOf(ac));
ac=st.pop();
}//栈取出的字符优先级比c低,则将取出的字符重新入栈
if(ac!=' '){
st.push(ac);
}
}st.push(c);//将c入栈
}//为操作数,直接串联到postfix内
else {
postfix=postfix.concat(String.valueOf(c));
}
}
}//当表达式读完就将算术栈pop出加入postfix
while(!st.isEmpty()){
postfix=postfix.concat(String.valueOf(st.pop()));

}
return postfix;
}
//对后缀表达式进行运算的函数
public double numberCalculate(String postfix)throws Exception{
Stack st=new Stack<>();//创建一个操作数栈
for(int i=0;postfix!=null&&i char c=postfix.charAt(i);
//如果为运算符
if(isOperator(c)&&!st.isEmpty()){
double d2=Double.valueOf(st.pop().toString());
double d1=Double.valueOf(st.pop().toString());
double d3=0;
if('+'==c){
d3=d1+d2;
}
if('-'==c){
d3=d1-d2;
}
if('/'==c){
d3=d1/d2;
}
if('*'==c){
d3=d1*d2;
}
if('%'==c){
d3=d1%d2;
}
if('^'==c){
d3=Math.pow(d1, d2);
}
//将运算结果压入操作数栈中
st.push(d3);
}else{//为操作数时直接压入操作数栈
st.push(c);}
}
return (double) st.pop();//返回运算结果
}
//判断字符为运算符
public boolean isOperator(char c){
if('+'==c||'-'==c||'/'==c||'*'==c||'%'==c||'^'==c){
return true;
}
else {
return false;
}
}
//判断字符为左括号
public boolean isOpenParent(char c){
return c=='(';
}
//判断字符为右括号
public boolean isCloseParent(char c){
return c==')';
}
//判断算法的优先级
public int priority(char c){
if(c=='^'){
return 3;
}
if(c=='/'||c=='*'||c=='%'){
return 2;
}
else if(c=='-'||c=='+'){
return 1;
}
else return 0;
}


public static void main(String[] args) throws Exception {
// TODO Auto-generated method stub
Example3_3 p=new Example3_3();
String postfix =p.converToPostfix("3+2*8+(5+5)+2^2/2*5%3");
System.out.println("表达式结果为:"+p.numberCalculate(postfix));
}
}运算结果
表达式结果为:30.0

微信扫一扫

第七城市微信公众平台