编译原理算符优先算法c++实现

编译原理中的算符优先算法通常用于解析表达式，它是一种处理语法结构的方法，特别是对于那些有明确优先级的运算符。在C++中，你可以使用递归下降分析法（Recursive Descent Parsing）来实现这种算法。以下是简单的步骤：

1. **定义状态机**：为每个可能的输入字符（如运算符、数字或变量名）创建一个状态，并规定当遇到这些字符时，解析器应该从当前状态转换到另一个状态。

2. **设置优先级队列**：C++的`std::stack`可以模拟一个后进先出（LIFO）的数据结构，但为了高效地处理优先级较高的运算符，我们可以使用`std::priority_queue`，其中元素按照优先级排序。

3. **解析函数**：编写一个解析函数，它接受输入流和操作数栈。当遇到一个非运算符的输入时，将其压入栈；如果遇到运算符，首先检查其是否大于当前队列顶的操作符优先级，如果是，则弹出队列中的所有优先级较低的运算符并将其结果与新的运算符结合，然后将新运算符加入队列。

4. **处理结束标志**：当输入流结束时，确保队列中只剩下一个运算符，这通常是整个表达式的终结符，例如`;`或`}`。

5. **构建表达式树**：最后，从栈中取出剩余的运算符及其对应的操作数，重构表达式为一棵树形结构，即可得到计算所需的中间表示形式。

#include <iostream>
#include <queue>
#include <stack>

// 定义一些基本的运算符优先级
enum class Priority { LOWEST, MIDDLE, HIGHEST };

Priority getPriority(char op) {
    // 根据实际的运算符优先级表填充这里
}

bool parseExpression(const std::string& input, int& result) {
    std::stack<int> operands;
    std::priority_queue<std::pair<char, int>, std::vector<std::pair<char, int>>, std::greater<std::pair<char, int>>> operators;

    for (char c : input) {
        if (isdigit(c)) { // 如果是数字，直接压入栈
            int num = 0;
            while (isdigit(c)) {
                num = num * 10 + c - '0';
                ++c;
            }
            operands.push(num);
        } else if (c == '+' || c == '-') { // 遇到运算符，处理它
            while (!operators.empty() && getPriority(operators.top().first) >= getPriority(c)) {
                int right = operands.pop();
                int left = operands.pop();
                char op = operators.top().first;
                operators.pop();
                operands.push(doOperation(left, right, op)); // 假设doOperation是一个实现了对应运算的函数
            }
            operators.push({c, operands.top()});
            operands.pop(); // 消耗掉上一个操作数
        } else if (c == '(') { // 开始一个新的表达式
            operators.push({c, operands.size()});
        } else if (c == ')') { // 结束一个表达式
            while (operators.top().first != '(') {
                int right = operands.pop();
                int left = operands.pop();
                char op = operators.top().first;
                operators.pop();
                operands.push(doOperation(left, right, op));
            }
            operators.pop(); // 弹出开始的左括号
        } else if (c == EOF) { // 输入结束，检查是否有未匹配的运算符
            return false;
        }
    }

    // 将剩余的运算符和操作数组合成最终结果
    while (!operators.empty()) {
        int right = operands.pop();
        int left = operands.pop();
        char op = operators.top().first;
        operators.pop();
        result = doOperation(left, right, op);
    }

    return true;
}

int main() {
    int res;
    std::string expression = "3 + 4 * 2";
    if (parseExpression(expression, res)) {
        std::cout << "Result: " << res << "\n";
    } else {
        std::cerr << "Invalid expression.\n";
    }
    return 0;
}