简单的四则运算(栈+逆波兰)

逆波兰利用栈实现简单的四则运算一．逆波兰表达式引自逆波兰表达式解决四则运算逆波兰表达式又叫做后缀表达式，它将复杂表达式转换为可以依靠简单的操作得到计算结果的表达式，解决了四则运算中括号改变运算符优先级的问题。四则运算的表达式一般都是中缀表达式如1+2*(3-4)+5，即操作符在两个操作数之间。四则运算需要两个步骤，一是把中缀表达式转为后缀表达式，二是由后缀表达生成结果中缀表达式转为后缀表达式算法描述：(1)首先有个包含中缀表达式元素列表sourceList,然后创建一个符号列表destList保存最终后缀表达式,创建一个操作符堆栈opStack(2)从sourceList取出一个元素A(3a)如是数字则加入到destList中(3b)如果元素A是运算符，将操作符A与操作符堆栈opStack栈顶的运算符的优先关系相比较。如果，优先关系高于opStack栈顶的运算符，则将该运算符压入操作符堆栈opStack。倘若不是(低于或等于)的话，则将运算符栈opStack栈顶的运算符从栈中弹出保存到destList，重复此步骤,直到作符A压入操作符堆栈opStack。(3c)若元素A是左括号(，则压入操作符堆栈opStack(3d)若元素B是右括号),则操作符堆栈opStack弹出操作符并加入到destList中，直到弹出左括号(。(5)从步骤2重复上述操作，所有元素处理完毕后将操作符堆栈opStack弹出操作符并加入到destList中，这样中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。示例：中缀表达式如1+2*(3-4)+5，构造元素列表1,+,2,*,(,3,-,4,),5,构造一个空最终后缀表达式destList，一个操作符堆栈opStack1、取出“1”，destList【1】，opStack【】2、取出“+”，destList【1】，opStack【+】3、取出“2”，destList【1,2】，opStack【+】4、取出“*”，destList【1,2】，opStack【+,*】5、取出“(”，destList【1,2】，opStack【+,*,(】6、取出“3”，destList【1,2,3】，opStack【+,*,(】7、取出“-”，destList【1,2,3】，opStack【+,*,(,-】8、取出“4”，destList【1,2,3,4】，opStack【+,*,(,-】9、取出“)”，destList【1,2,3,4,-】，opStack【+,*】//操作符堆栈opStack弹出操作符并加入到destList中，直到弹出左括号(10、取出“+”，destList【1,2,3,4,-,*,+】，opStack【+】//加号优先级不大于【+,*】11、取出“5”，destList【1,2,3,4,-,*,+,5】，opStack【+】12、处理完毕，destList【1,2,3,4,-,*,+,5,+】，opStack【】后缀表达式到计算结果算法描述：遍历储存后缀表达式的列表，将元素依次进栈，当遇到操作符时，连续出栈两个元素，进行运算，再将结果进栈，最后栈内留下的元素就是计算结果示例：后缀表达式destList【1,2,3,4,-,*,+,5,+】，结果堆栈resultStatck【】格式输入--:结果[1,2,3,4]--:resultStatck【1,2,3,4】[-]--:resultStatck【1,2,3-4】[*]--:resultStatck【1,2*(3-4)】[+]--:resultStatck【1+2*(3-4)】[5]--:resultStatck【1+2*(3-4),5】[+]--:resultStatck【1+2*(3-4)+5】举例：正常的表达式逆波兰表达式a+b---a,b,+a+(b-c)---a,b,c,-,+a+(b-c)*d---a,b,c,-,d,*,+a+d*(b-c)---a,d,b,c,-,*,+a=1+3---a=1,3+二．自己写的简单四则运算的程序。//逆波兰利用栈实现简单的四则运算#includeiostream#includestring#includestack#includectype.husingnamespacestd;voidchangebolan(char*sourcelist,char*destlist,intn){stackchars;inti=0,j=0;while(sourcelist[i]!='\0'){if(isdigit(sourcelist[i])){destlist[j]=sourcelist[i];i++;j++;//如果是数字的话直接放到destlist中，然后取sourcelist的下一个符号}else{if((sourcelist[i]=='+')||(sourcelist[i]=='-')){while((!s.empty())&&s.top()!='(')//如果是加减号的话，只要不遇到'('或者栈空的情况下，连续弹出栈内的符号，因为加减号是优先级最低的，不可能大于栈内的符号。{destlist[j]=s.top();j++;s.pop();}s.push(sourcelist[i]);//栈内取光了或者遇到了'('，压栈，然后处理sourcelist的下一个符号i++;}if(sourcelist[i]=='*'||sourcelist[i]=='/'){while((!s.empty())&&(s.top()=='*'||s.top()=='/'))//如果是乘除的话，遇到乘除就会弹出栈内的，到destlist中，因为等于栈内的，需弹出栈内的，{destlist[j]=s.top();j++;s.pop();}s.push(sourcelist[i]);//说明遇到了不是乘除的情况，也就是空栈或者'('或者加减。此时都需要直接压栈。然后取出sourcelist的下一个符号i++;}if(sourcelist[i]=='(')//如果是'('直接压栈{s.push(sourcelist[i]);i++;}if(sourcelist[i]==')'){while((s.top()!='(')&&(!s.empty()))//如果是'）'就将栈内遇到'('前的所有元素弹出，到destlist中。{destlist[j]=s.top();j++;s.pop();}if(!s.empty()){s.pop();//将栈内的'('删除，注意不要存进destlist中了、i++;}}}}while(!s.empty()){destlist[j]=s.top();s.pop();j++;}destlist[j]='\0';}intcompute(char*destlist,intn){stackintT;inti=0;intw=0;while(destlist[i]!='\0'){if(isdigit(destlist[i]))//如果是数字字符，转化成int数字压栈，然后转向下一个字符。{w=destlist[i]-'0';T.push(w);i++;}else{intTF=0,TS=0,m=0;TF=T.top();T.pop();TS=T.top();T.pop();//取出栈中的前两个数据if(destlist[i]=='+')m=TS+TF;if(destlist[i]=='-')m=TS-TF;if(destlist[i]=='*')m=TS*TF;if(destlist[i]=='/')m=TS/TF;//以上的运算由于栈的原因都是后取出的与前面的做运算。T.push(m);//将两个数的计算结果作为一个新的数压栈，与栈中的其他数再运算。然后判断下一个字符。i++;}}returnT.top();}voidmain(){char*sourcelist=newchar[100];cout请输入字符串表达式endl;cinsourcelist;intn=strlen(sourcelist);char*destlist=newchar[n+1];changebolan(sourcelist,destlist,n);cout得到的逆波兰表达式为destlist;coutendl;intm=compute(destlist,n);coutsourcelist;cout=m;}//输入字符串1+2*(3-4)+5//输出的逆波兰,2,3,4,-,*,+,5,+//最终结果+2*(3-4)+5=4