用链栈实现表达式求值

使用链栈实现表达式求值的基本思路是，将中缀表达式转换为后缀表达式，然后再利用后缀表达式进行求值。具体步骤如下：

1. 定义两个链栈，一个用于存储运算数（OPND），一个用于存储运算符（OPTR）。

2. 将中缀表达式转换为后缀表达式。具体方法是，从左到右扫描中缀表达式的每个元素，如果是运算数，则直接输出；如果是运算符，则将其与OPTR栈顶元素进行比较，如果优先级高于栈顶元素，则将其入栈；否则将OPTR栈顶元素弹出并输出，直到栈顶元素优先级低于该运算符，然后将该运算符入栈。如果遇到左括号，则直接入栈；如果遇到右括号，则将OPTR栈顶元素弹出并输出，直到遇到左括号为止。

3. 对后缀表达式进行求值。具体方法是，从左到右扫描后缀表达式的每个元素，如果是运算数，则将其入OPND栈；如果是运算符，则将OPND栈顶的两个元素弹出进行运算，并将结果入栈。

下面是使用C++实现的代码，该代码仅适用于个位数（整型）表达式求值：

#include <iostream>
#include <stack>
#include <string>
using namespace std;

bool In(char ch) {
    if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(' || ch == ')' || ch == '#') {
        return true;
    } else {
        return false;
    }
}

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

int Operate(int a, int b, char op) {
    switch (op) {
        case '+':
            return a + b;
        case '-':
            return a - b;
        case '*':
            return a * b;
        case '/':
            return a / b;
        default:
            return 0;
    }
}

int EvaluateExpression(string exp) {
    stack<int> OPND;
    stack<char> OPTR;
    OPTR.push('#');
    int i = 0;
    while (i < exp.length()) {
        if (!In(exp[i])) {
            int num = 0;
            while (i < exp.length() && !In(exp[i])) {
                num = num * 10 + exp[i] - '0';
                i++;
            }
            OPND.push(num);
        } else {
            char op = exp[i];
            if (op == '(') {
                OPTR.push(op);
                i++;
            } else if (op == ')') {
                while (OPTR.top() != '(') {
                    int b = OPND.top();
                    OPND.pop();
                    int a = OPND.top();
                    OPND.pop();
                    char op = OPTR.top();
                    OPTR.pop();
                    OPND.push(Operate(a, b, op));
                }
                OPTR.pop();
                i++;
            } else {
                if (Priority(op) > Priority(OPTR.top())) {
                    OPTR.push(op);
                    i++;
                } else {
                    int b = OPND.top();
                    OPND.pop();
                    int a = OPND.top();
                    OPND.pop();
                    char op2 = OPTR.top();
                    OPTR.pop();
                    OPND.push(Operate(a, b, op2));
                }
            }
        }
    }
    while (OPTR.top() != '#') {
        int b = OPND.top();
        OPND.pop();
        int a = OPND.top();
        OPND.pop();
        char op = OPTR.top();
        OPTR.pop();
        OPND.push(Operate(a, b, op));
    }
    return OPND.top();
}

int main() {
    string exp = "3+4*5-6/2";
    int result = EvaluateExpression(exp);
    cout << result << endl;
    return 0;
}