中綴轉(zhuǎn)后綴：
表達(dá)式求值：
代碼：（輸入#號(hào)結(jié)束）
#include <iostream>
#include <cstring>
#include <stack>
#include <queue>
#include <stdio.h>
using namespace std;
stack<string> fuhao;
stack<double> suansu;
queue<string> houzhui;
//判斷兩個(gè)符號(hào)的優(yōu)先級(jí)
bool youji(string a,string b){
? ? if(a=="+"||a=="-"){
? ? ? ? if(b=="+"||b=="-"){
? ? ? ? ? ? return true;
? ? ? ? }else{
? ? ? ? ? ? return false;
? ? ? ? }
? ? }
? ? if(a=="*"||a=="/"){
? ? ? ? if(b=="+"||b=="-"||b=="*"||b=="/"){
? ? ? ? ? ? return true;
? ? ? ? }
? ? }
? ? if(b=="("||a=="("){
? ? ? ? return false;
? ? }
}
//判斷字符串是否是數(shù)字字符串
bool p_shuzi(string s){
? ? bool b=true;
? ? int s_len=s.size();
? ? for(int i=0;i<s_len;i++){
? ? ? ? if(s[i]>='0'&&s[i]<='9'){
? ? ? ? ? ? continue;
? ? ? ? }else{
? ? ? ? ? ? b=false;
? ? ? ? ? ? break;
? ? ? ? }
? ? }
? ? return b;
}
//中綴轉(zhuǎn)后綴
void zhuan_hou(){
? ? string s[100]; //輸入中綴表達(dá)式，用字符串處理，是為了可以輸入多位以上的數(shù)字
? ? //初始化s
? ? for(int i=0;i<100;i++){
? ? ? ? s[i]="|";
? ? }
? ? int j;
? ? for(j=0;j<100;j++){ //輸入#號(hào)退出
? ? ? ? char temp1[100];
? ? ? ? int i=0;
? ? ? ? while(1){
? ? ? ? ? ? cin>>temp1[i];
? ? ? ? ? if(temp1[i]=='+'||temp1[i]=='-'||temp1[i]=='*'||temp1[i]=='/'||temp1[i]=='('||temp1[i]==')'||temp1[i]=='#'){
? ? ? ? ? ? ? ? if(s[j]=="|"){//處理碰到*(的情況，連續(xù)兩個(gè)符號(hào)的問(wèn)題
? ? ? ? ? ? ? ? ? ? s[j]=temp1[i];
? ? ? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? ? ? s[++j]=temp1[i];
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? break;
? ? ? ? ? }else{
? ? ? ? ? ? ? if(s[j]=="|"){//處理碰到是數(shù)字的情況
? ? ? ? ? ? ? ? ? ? s[j]="";
? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? s[j]+=temp1[i++];
? ? ? ? ? }
? ? ? ? }
? ? ? ? if(s[j]=="#"){
? ? ? ? ? ? break;
? ? ? ? }
? ? }
? ? int len=j+1;
? // cout<<len;
? ? //中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式
? ? for(int i=0;i<len;i++){
? ? ? ? //cout<<s[i];
? ? ? ? if(s[i]=="#"){
? ? ? ? ? ? //把符號(hào)棧中剩余的都進(jìn)入
? ? ? ? ? ? while(!fuhao.empty()){
? ? ? ? ? ? ? ? houzhui.push(fuhao.top());
? ? ? ? ? ? ? ? fuhao.pop();
? ? ? ? ? ? }
? ? ? ? ? ? break;
? ? ? ? }
? ? ? ? if(p_shuzi(s[i])){ //遇到數(shù)字進(jìn)棧
? ? ? ? ? ? houzhui.push(s[i]);
? ? ? ? ? ? continue;
? ? ? ? }
? ? ? ? if((s[i]=="+"||s[i]=="-"||s[i]=="*"||s[i]=="/"||s[i]=="(")&&fuhao.empty()){ //遇到這些符號(hào)并且符號(hào)棧為空的時(shí)候進(jìn)符號(hào)棧
? ? ? ? ? ? fuhao.push(s[i]);
? ? ? ? ? ? continue;
? ? ? ? }
? ? ? ? if(s[i]==")"){
? ? ? ? ? ? while(fuhao.top()!="("){
? ? ? ? ? ? ? ? houzhui.push(fuhao.top());
? ? ? ? ? ? ? ? fuhao.pop();
? ? ? ? ? ? }
? ? ? ? ? ? fuhao.pop();
? ? ? ? ? ? continue;
? ? ? ? }
? ? ? ? while(youji(fuhao.top(),s[i])){
? ? ? ? ? ? houzhui.push(fuhao.top());
? ? ? ? ? ? fuhao.pop();
? ? ? ? ? ? if(fuhao.empty()){
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? fuhao.push(s[i]);//符號(hào)入棧
? ? }
//? ? ? ? while(!houzhui.empty()){
//? ? ? ? ? ? cout<<houzhui.front();
//? ? ? ? ? ? houzhui.pop();
//? ? ? ? }
}
void jisuan(){
? ? //用后綴表達(dá)式求值
? ? while(!houzhui.empty()){
? ? ? ? string ch=houzhui.front();
? ? ? ? //cout<<houzhui.size();
? ? ? ? if(p_shuzi(ch)){
? ? ? ? ? ? double num1;
? ? ? ? ? ? int ch_len=ch.size();
? ? ? ? ? ? char *ch1=new char[ch_len];
? ? ? ? ? ? for(int i=0;i<ch_len;i++){
? ? ? ? ? ? ? ? ch1[i]=ch[i];
? ? ? ? ? ? }
? ? ? ? ? ? //把數(shù)字字符串轉(zhuǎn)為數(shù)字
? ? ? ? ? ? sscanf(ch1,"%lf",&num1);
? ? ? ? ? ? //cout<<num1<<"std"<<endl;
? ? ? ? ? ? suansu.push(num1);
? ? ? ? ? ? houzhui.pop();
? ? ? ? }else{
? ? ? ? ? ? houzhui.pop();
? ? ? ? ? ? double num2=suansu.top();
? ? ? ? ? ? suansu.pop();
? ? ? ? ? ? double num1=suansu.top();
? ? ? ? ? ? suansu.pop();
? ? ? ? ? ? double jieguo;
? ? ? ? ? ? //cout<<num1<<ch<<num2;
? ? ? ? ? ? if(ch=="+"){
? ? ? ? ? ? ? ? jieguo=num1+num2;
? ? ? ? ? ? }else if(ch=="-"){
? ? ? ? ? ? ? ? jieguo=num1-num2;
? ? ? ? ? ? }else if(ch=="*"){
? ? ? ? ? ? ? ? jieguo=num1*num2;
? ? ? ? ? ? }else if(ch=="/"){
? ? ? ? ? ? ? ? jieguo=num1/num2;
? ? ? ? ? ? }
? ? ? ? ? // cout<<jieguo<<endl;
? ? ? ? ? ? suansu.push(jieguo);
? ? ? ? }
? ? }
? ? cout<<suansu.top()<<endl;
}
int main(){
? ? int m=3;
? ? while(m--){
? ? ? ? //每次計(jì)算完成之后刃鳄，都需要將棧和隊(duì)列清空
? ? ? ? while(!fuhao.empty())fuhao.pop();
? ? ? ? while(!suansu.empty())suansu.pop();
? ? ? ? while(!houzhui.empty())houzhui.pop();
? ? ? ? zhuan_hou(); //中綴轉(zhuǎn)成后綴
? ? ? ? jisuan(); //使用后綴進(jìn)行計(jì)算
? ? }
? ? return 0;
}
測(cè)試結(jié)果：
測(cè)試后綴的時(shí)候，把我后綴函數(shù)中最后那幾行注釋打開(kāi)事示，然后把主函數(shù)中的jisuan函數(shù)注釋了黍判，就可以測(cè)試后綴了
