实验四 算符优先分析法设计与实现C++

算符优先分析法（Operator-precedence parsing）是一种自底向上的语法分析方法，用于判断一个表达式是否符合语法规则。它通过比较运算符之间的优先级来确定表达式的结构，从而构建语法树。

以下是算符优先分析法的基本思路：

1. 定义运算符之间的优先级关系，通常用数字表示，数字越大表示优先级越高。
2. 从左到右扫描表达式，遇到操作数则将其压入栈中，遇到操作符则进行以下操作：
- 如果栈为空，则将操作符压入栈中。
- 如果栈顶是左括号，则将操作符压入栈中。
- 如果操作符优先级高于栈顶元素，则将操作符压入栈中。
- 如果操作符优先级低于或等于栈顶元素，则将栈顶元素弹出，直到栈为空或栈顶元素优先级低于该操作符，然后将操作符压入栈中。
- 如果操作符是右括号，则将栈顶元素弹出，直到遇到左括号为止。
3. 扫描结束后，将栈中剩余的元素依次弹出，构建语法树。

下面是一个简单的算符优先分析法的实现，用于计算表达式的值：

#include <iostream>
#include <stack>
#include <map>
#include <string>

using namespace std;

// 定义运算符优先级
map<char, int> priority = {
    {'+', 1},
    {'-', 1},
    {'*', 2},
    {'/', 2},
    {'(', 0}
};

// 计算表达式的值
int calculate(int left, int right, char op) {
    switch (op) {
        case '+':
            return left + right;
        case '-':
            return left - right;
        case '*':
            return left * right;
        case '/':
            return left / right;
        default:
            return 0;
    }
}

// 算符优先分析法
int operator_precedence(string expr) {
    stack<int> nums; // 存放操作数的栈
    stack<char> ops; // 存放运算符的栈
    for (int i = 0; i < expr.size(); i++) {
        char c = expr[i];
        if (isdigit(c)) { // 如果是数字，将其转化为整数并压入栈中
            int num = c - '0';
            while (i + 1 < expr.size() && isdigit(expr[i + 1])) {
                num = num * 10 + (expr[i + 1] - '0');
                i++;
            }
            nums.push(num);
        } else if (c == '(') { // 如果是左括号，将其压入栈中
            ops.push(c);
        } else if (c == ')') { // 如果是右括号，将栈顶的运算符弹出，直到遇到左括号为止
            while (ops.top() != '(') {
                char op = ops.top();
                ops.pop();
                int right = nums.top();
                nums.pop();
                int left = nums.top();
                nums.pop();
                nums.push(calculate(left, right, op));
            }
            ops.pop(); // 弹出左括号
        } else { // 如果是运算符
            while (!ops.empty() && priority[c] <= priority[ops.top()]) {
                char op = ops.top();
                ops.pop();
                int right = nums.top();
                nums.pop();
                int left = nums.top();
                nums.pop();
                nums.push(calculate(left, right, op));
            }
            ops.push(c); // 将运算符压入栈中
        }
    }
    while (!ops.empty()) { // 将栈中剩余的运算符依次弹出
        char op = ops.top();
        ops.pop();
        int right = nums.top();
        nums.pop();
        int left = nums.top();
        nums.pop();
        nums.push(calculate(left, right, op));
    }
    return nums.top(); // 返回最终结果
}

int main() {
    string expr = "3*(2+1)-2*(4-1)";
    int result = operator_precedence(expr);
    cout << "Expression: " << expr << endl;
    cout << "Result: " << result << endl;
    return 0;
}

运行结果：

Expression: 3*(2+1)-2*(4-1)
Result: 3

上面的代码仅支持四则运算和括号，如果要支持更多的运算符，只需在优先级表中添加对应的优先级即可。