编译原理实验（四）——中间代码生成程序（逆波兰表示）

谁借莪１个温暖的怀抱￠ 2023-05-30 09:16 92阅读 0赞

### 编译原理实验（四）——中间代码生成程序（逆波兰表示） ###

*   *   *  实验要求
         *  参考程序
         *  实验截图

### 实验要求 ###

编制一个中间代码生成程序，能将算术表达式等翻译成逆波兰形式；

### 参考程序 ###

#include <iostream>
    #include <vector>
    #include <stack>
    #include <map>
    using namespace std;
    struct node
    {                 //定义结构体，该结构体用于存储每次处理的字符
        char op;     //如果是操作符，存入到op中，并且要将flag置为false
        double data; //如果是操作数，存入到data中，并且要将flag置为true
        bool flag;
    };
    
    stack<node> s;     //操作符栈，存放操作符的临时工作栈。
    vector<node> q;    //后缀表达式队列 为了保留结果且便于输出 用vector数组模拟队列行为
    map<char, int> op; //操作符优先级
    
    void RPN(string str)
    { 
        q.clear();
        int len = str.length();
        bool f = false;
        for (int i = 0; i < len;)
        { 
            node temp;
            if (str[i] >= '0' && str[i] <= '9')
            {                                //如果是操作数的话
                temp.flag = true;           //标记置为true
                temp.data = str[i++] - '0'; //存储到临时结构体temp中
                int flag = 1;
                double x = 0.1;
                while (i < len)
                {  //因为数字可能不止一位，因此循环至不是数字为止
                    if (str[i] == '.')
                        flag = 0;
                    else if (str[i] >= '0' && str[i] <= '9')
                    { 
                        if (flag)
                            temp.data = temp.data * 10 + (str[i] - '0');
                        else
                            temp.data += (str[i] - '0') * x, x *= 0.1;
                    }
                    else
                        break;
                    i++;
                }
                q.push_back(temp); //将该操作数扔进后缀序列的队列中
                f = false;
            }
            else if (str[i] == '(')
            { 
                temp.flag = false;
                temp.op = str[i]; //是左括号直接压入栈
                s.push(temp);
                i++;
                f = false;
            }
            else if (str[i] == ')')
            {  //终于等到了右括号
                while (s.top().op != '(')
                {  //将栈里面的操作符弹出到后缀表达式中，直到碰到了左括号
                    q.push_back(s.top());
                    s.pop();
                }
                s.pop(); //扔掉左括号
                i++;
                f = false;
            }
            else
            { 
                if (i == 0)
                { 
                    cout << "运算符不能开头" << endl;
                    return;
                }
                if (f == true)
                { 
                    cout << "运算符连续出现" << endl;
                    return;
                }
                f = true;
                temp.flag = false; //如果是操作符，那么标记置为false
                while (!s.empty() && op[str[i]] <= op[s.top().op])
                {                          //只有当该操作符的优先级高于栈顶元素的优先级，才压入栈内
                    q.push_back(s.top()); //否则将栈顶元素弹出，压入到队列中
                    s.pop();
                }
                temp.op = str[i];
                s.push(temp);
                i++;
            }
        }
        while (!s.empty())
        {  //最后如果操作符栈还不空的话。依次弹出压入到队列中
            q.push_back(s.top());
            s.pop();
        }
        cout << "该中缀表达式的逆波兰表达式为：\n";
        for (int i = 0; i < q.size(); ++i)
        { 
            if (q[i].flag)
                cout << q[i].data << " ";
            else
                cout << q[i].op << " ";
        }
        cout << endl;
    }
    
    int main()
    { 
        op['+'] = op['-'] = 10; //输入操作符优先级
        op['*'] = op['/'] = 20;
        while (1)
        { 
            cout << "请输入中缀表达式：\n";
            string str;
            cin >> str;
            cout << str << endl;
            RPN(str);
            cout << "是否进行分析(y)" << endl;
            char c;
            cin >> c;
            cout << c << endl;
            if (c != 'y')
                break;
        }
        return 0;
    }

### 实验截图 ###

![在这里插入图片描述][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/20191130102657547.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw,size_16,color_FFFFFF,t_70