中缀式转波兰式编译原理课程设计

中缀式转波兰式是编译原理中的一个重要概念，它是实现算术表达式计算的一种方法。在编译原理课程设计中，可以设计一个简单的中缀式转波兰式的编译器。

设计思路：

1. 建立一个栈S和一个列表L，用于存储操作符和操作数。
2. 从左到右遍历中缀式中的每个元素：
- 如果是数字，直接加入列表L中。
- 如果是左括号，将其压入栈S中。
- 如果是右括号，则将栈S中的元素弹出并加入列表L中，直到遇到左括号为止。注意：左括号不加入列表L中。
- 如果是操作符，比较其与栈顶操作符的优先级。如果该操作符优先级高于栈顶操作符，则将其压入栈S中。否则将栈S中的操作符弹出并加入列表L中，直到栈S为空或栈顶操作符优先级低于该操作符。
3. 重复步骤2，直到中缀式中所有元素都被遍历。
4. 如果栈S中还有元素，则依次弹出并加入列表L中。
5. 得到的列表L就是对应的波兰式。

代码实现：

以下是一个简单的中缀式转波兰式的编译器的C++代码实现。其中，用vector模拟了列表L，用stack模拟了栈S。

#include <iostream>
#include <vector>
#include <stack>
#include <string>

using namespace std;

// 定义运算符的优先级
int priority(char op) {
    if (op == '+' || op == '-') {
        return 1;
    } else if (op == '*' || op == '/') {
        return 2;
    } else {
        return 0;
    }
}

// 中缀表达式转后缀表达式
vector<string> infixToPostfix(string infix) {
    vector<string> postfix;
    stack<char> s;
    for (int i = 0; i < infix.length(); i++) {
        char c = infix[i];
        if (isdigit(c)) {
            // 如果是数字，直接加入列表L中
            string num = "";
            while (isdigit(c)) {
                num += c;
                i++;
                c = infix[i];
            }
            i--;
            postfix.push_back(num);
        } else if (c == '(') {
            // 如果是左括号，则将其压入栈S中
            s.push(c);
        } else if (c == ')') {
            // 如果是右括号，则将栈S中的元素弹出并加入列表L中，直到遇到左括号为止。注意：左括号不加入列表L中。
            while (s.top() != '(') {
                postfix.push_back(string(1, s.top()));
                s.pop();
            }
            s.pop();
        } else {
            // 如果是操作符，比较其与栈顶操作符的优先级。如果该操作符优先级高于栈顶操作符，则将其压入栈S中。否则将栈S中的操作符弹出并加入列表L中，直到栈S为空或栈顶操作符优先级低于该操作符。
            while (!s.empty() && priority(c) <= priority(s.top())) {
                postfix.push_back(string(1, s.top()));
                s.pop();
            }
            s.push(c);
        }
    }
    while (!s.empty()) {
        // 如果栈S中还有元素，则依次弹出并加入列表L中。
        postfix.push_back(string(1, s.top()));
        s.pop();
    }
    return postfix;
}

int main() {
    string infix = "1+(2-3)*4/5";
    vector<string> postfix = infixToPostfix(infix);
    cout << "中缀式: " << infix << endl;
    cout << "后缀式: ";
    for (int i = 0; i < postfix.size(); i++) {
        cout << postfix[i] << " ";
    }
    cout << endl;
    return 0;
}

运行结果：

中缀式: 1+(2-3)*4/5
后缀式: 1 2 3 - 4 * 5 / +