数据结构中缀表达式求值

中缀表达式求值是指将一个中缀表达式转换为后缀表达式，并计算后缀表达式的值的过程。具体步骤如下：

1. 创建一个操作数栈和一个运算符栈。
2. 从左到右扫描中缀表达式的每个元素。
3. 如果当前元素是操作数，则将其压入操作数栈中。
4. 如果当前元素是运算符，则进行如下操作：
1. 如果运算符栈为空，或者栈顶运算符为左括号，则将当前运算符压入运算符栈中。
2. 如果当前运算符的优先级大于栈顶运算符的优先级，则将当前运算符压入运算符栈中。
3. 否则，将运算符栈顶的运算符弹出并压入操作数栈中，直到当前运算符的优先级大于栈顶运算符的优先级。
5. 如果当前元素是左括号，则将其压入运算符栈中。
6. 如果当前元素是右括号，则进行如下操作：
1. 将运算符栈顶的运算符弹出并压入操作数栈中，直到遇到左括号。
2. 将左括号弹出，但不压入操作数栈中。
7. 如果中缀表达式的所有元素都已经扫描完毕，则将运算符栈中的所有运算符依次弹出并压入操作数栈中。
8. 最后，操作数栈中的唯一元素就是中缀表达式的值。

下面是一个示例中缀表达式求值的代码实现，使用C++模板类实现操作数栈和运算符栈：

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

using namespace std;

template<typename T>
class Stack {
public:
    Stack(int n) {
        elem = new T[n];
        top = -1;
        max_size = n;
    }

    ~Stack() {
        delete[] elem;
    }

    bool push(T x) {
        if (top == max_size - 1) {
            return false;
        }
        elem[++top] = x;
        return true;
    }

    bool pop(T& x) {
        if (top == -1) {
            return false;
        }
        x = elem[top--];
        return true;
    }

    bool top(T& x) {
        if (top == -1) {
            return false;
        }
        x = elem[top];
        return true;
    }

    bool empty() {
        return top == -1;
    }

private:
    T* elem;
    int top;
    int max_size;
};

int priority(char op) {
    switch (op) {
    case '+':
    case '-':
        return 1;
    case '*':
    case '/':
        return 2;
    default:
        return 0;
    }
}

int evaluate(string expr) {
    Stack<int> opnd(expr.length());
    Stack<char> optr(expr.length());
    int i = 0;
    while (i < expr.length()) {
        if (isdigit(expr[i])) {
            int num = 0;
            while (i < expr.length() && isdigit(expr[i])) {
                num = num * 10 + (expr[i] - '0');
                i++;
            }
            opnd.push(num);
        }
        else if (expr[i] == '(') {
            optr.push(expr[i]);
            i++;
        }
        else if (expr[i] == ')') {
            char op;
            optr.pop(op);
            while (op != '(') {
                int b, a;
                opnd.pop(b);
                opnd.pop(a);
                switch (op) {
                case '+':
                    opnd.push(a + b);
                    break;
                case '-':
                    opnd.push(a - b);
                    break;
                case '*':
                    opnd.push(a * b);
                    break;
                case '/':
                    opnd.push(a / b);
                    break;
                }
                optr.pop(op);
            }
            i++;
        }
        else if (expr[i] == '+' || expr[i] == '-' || expr[i] == '*' || expr[i] == '/') {
            char op = expr[i];
            while (!optr.empty() && optr.top() != '(' && priority(op) <= priority(optr.top())) {
                int b, a;
                opnd.pop(b);
                opnd.pop(a);
                char op2;
                optr.pop(op2);
                switch (op2) {
                case '+':
                    opnd.push(a + b);
                    break;
                case '-':
                    opnd.push(a - b);
                    break;
                case '*':
                    opnd.push(a * b);
                    break;
                case '/':
                    opnd.push(a / b);
                    break;
                }
            }
            optr.push(op);
            i++;
        }
        else {
            i++;
        }
    }
    while (!optr.empty()) {
        int b, a;
        opnd.pop(b);
        opnd.pop(a);
        char op;
        optr.pop(op);
        switch (op) {
        case '+':
            opnd.push(a + b);
            break;
        case '-':
            opnd.push(a - b);
            break;
        case '*':
            opnd.push(a * b);
            break;
        case '/':
            opnd.push(a / b);
            break;
        }
    }
    int result;
    opnd.pop(result);
    return result;
}

int main() {
    string expr = "3+4*5-(6+7)*8/9";
    int result = evaluate(expr);
    cout << result << endl;
    return 0;
}