编译原理实验：中间代码生成——逆波兰表达式

向右看齐 2023-06-21 07:28 77阅读 0赞

### 编译原理实验：中间代码生成——逆波兰表达式 ###

*   *  逆波兰表达式
     *  测试

## 逆波兰表达式 ##

*  运算对象写在前，运算符写在后(后缀表示形式)  
    例如：a+b  → \\rightarrow → ab+  
    　　(a+b)*c  → \\rightarrow → ab+c*  
    　　a+b*c  → \\rightarrow → abc*\+  
    　　a=b*c+b*d  → \\rightarrow → abc*bd*\+=
 *  优点：易于计算机处理  
    利用栈，将扫描到的运算对象入栈，碰到运算符：  
    若是双目运算符，则对栈顶的两个运算对象实施该运算并将运算结果代替这两个运算对象进栈；  
    若是单目运算符，对栈顶元素，执行该运算，将运算结果代替该元素进栈，最后结果即栈顶元素。

c++代码：

#include<string>
    #include<iostream>
    #include<map>
    #include<stack>
    #include<vector>
    using namespace std;
    string str; //需要进行分析的算术表达式
    stack<char> tem; //当无法确定运算符是否要输出的时候，将运算符进栈
    vector<string> exp;//逆波兰表达式序列
    map<char,int> opPri;//定义预定义运算符的优先级
    bool convert();//将中缀表达式转化成逆波兰表达式，返回值fasle表示表达式存在错误
    bool isLet(char c){ 
        return (c>='A'&&c<='Z')||(c>='a'&&c<='z');
    }//判断字符是否为字母
    bool isId(char c){ 
        return isLet(c)||c=='_';
    }//判断字符是否为字母或者为下划线，是否为标识符的一部分
    bool isDigit(char c){ 
        return c>='0'&&c<='9';
    }//判断字符是否为数字
    int main(){ 
        opPri['(']=opPri[')']=1;
        opPri['+']=opPri['-']=100;
        opPri['*']=opPri['/']=200;
        while(true){ 
            cout<<"请输入算术表达式\n";getline(cin,str);
            if(convert()){ 
                cout<<"分析完毕,该表达式的后缀表达式为:\n";
                for(int i=0;i<exp.size();++i)cout<<exp[i]<<" ";cout<<endl;
            }
            cout<<"是否继续进行分析(y)\n";getline(cin,str);
            if(str!="y")break;
        }
    }
    bool convert(){ 
        int len=str.length();bool f1=false,f2=false;
        string word;exp.clear();while(!tem.empty())tem.pop();
        for(int i=0;i<len;){ 
            if(str[i]==' '||str[i]==9){ 
                i++;continue;
            }//忽略空格、tab
            if(isId(str[i])){    
                word="";
                while(i<len&&(isId(str[i])||isDigit(str[i])))word+=str[i++];
                if(i<len&&str[i]=='('){ 
                    cout<<"表达式错误，’(‘前面应该为运算符"<<endl;return false;
                }else if(f1==true){ 
                    cout<<"表达式错误，标识符(数字)之间应该有运算符"<<endl;return false;
                }
                f1=true;f2=false;
                exp.push_back(word); 
            }else if(isDigit(str[i])){ 
                word="";
                while(i<len&&isDigit(str[i]))word+=str[i++];
                if(i<len&&str[i]=='.'){ 
                    word+='.';++i;if(i==len||(isDigit(str[i])==false)){ 
                        cout<<"表达式错误,浮点数表达错误"<<endl;return false;
                    }
                    while(i<len&&isDigit(str[i]))word+=str[i++];
                    if(i<len&&(isId(str[i])||str[i]=='.')){ 
                        cout<<"表达式错误,浮点数表达错误"<<endl;return false;
                    }else if(f1){ 
                        cout<<"表达式错误，标识符(数字)之间应该有运算符"<<endl;return false;
                    }
                    f1=true;f2=false;
                    exp.push_back(word); 
                }else if(i<len&&isId(str[i])){ 
                    cout<<"表达式错误，数字之间跟字母"<<endl;return false;
                }else if(f1){ 
                    cout<<"表达式错误，标识符(数字)之间应该有运算符"<<endl;return false;
                }else if(i<len&&str[i]=='('){ 
                    cout<<"表达式错误，’(‘前面应该为运算符"<<endl;return false;
                }
                f1=true;f2=false;
                exp.push_back(word); 
            }else if(str[i]=='('){ 
                tem.push(str[i++]);
            }else if(str[i]==')'){ 
                while(!tem.empty()&&tem.top()!='('){ 
                    word="";word+=tem.top();tem.pop();exp.push_back(word);
                }
                if(tem.empty()){ 
                    cout<<"表达式错误，')'前面缺少'('。\n";return false;
                }
                tem.pop();
                ++i;
            }else{ 
                if(opPri.find(str[i])==opPri.end()){ 
                    cout<<"表达式错误，出现非法字符\n";return false;
                }
                if(f2==true){ 
                    cout<<"表达式错误，出现连续的运算符\n";return false;
                }
                while(!tem.empty()&&opPri[str[i]]<=opPri[tem.top()]){ 
                    word="";word+=tem.top();tem.pop();exp.push_back(word);
                }
                tem.push(str[i++]);f1=false,f2=true;
            }
        }
        while(!tem.empty()){ 
            if(tem.top()=='('){ 
                cout<<"表达式错误，'('后面缺少')'。\n";return false;
            }
            word="";word+=tem.top();tem.pop();exp.push_back(word);
        }return true;
    }

## 测试 ##

测试数据:

a+4.+
    y
    a+7+8+(+
    y
    a + 4 +(sf+d))
    y
    a33+d3+34f
    y
    1 e + 4
    y
    (a+4+(d*4)+5)+8
    n

截图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191211185219883.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw,size_16,color_FFFFFF,t_70