数据结构学习（C++）——栈应用（表达式求值） (转)

好的，下面是关于栈应用（表达式求值）的学习笔记。

## 1. 表达式求值的基本概念

### 1.1 中缀表达式

中缀表达式是我们平时写的表达式，如：2 + 3 * 4 - 6 / 2。

### 1.2 后缀表达式

后缀表达式也叫逆波兰表达式，它是一种不包含括号的表达式。在后缀表达式中，运算符在操作数的后面，因此也叫后缀表示法。例如，上面的中缀表达式的后缀表达式为：2 3 4 * + 6 2 / -。

### 1.3 前缀表达式

前缀表达式也叫波兰式，它与后缀表达式类似，只是运算符在操作数的前面。例如，上面的中缀表达式的前缀表达式为：- + * 3 4 2 / 6 2。

### 1.4 运算符优先级

在中缀表达式中，运算符有不同的优先级。通常，乘法和除法的优先级高于加法和减法。如果有括号，则括号内的表达式优先计算。

### 1.5 中缀表达式转后缀表达式

将中缀表达式转换成后缀表达式的过程，也叫中缀表达式的后缀表达式化。具体的转换规则如下：

- 遍历中缀表达式的每个元素。
- 如果当前元素是操作数，则将其加入后缀表达式中。
- 如果当前元素是运算符，则判断其与栈顶运算符的优先级，如果栈顶运算符优先级高于或等于当前运算符，则弹出栈顶运算符加入后缀表达式中，并继续比较下一个栈顶运算符，直到当前运算符的优先级高于栈顶运算符或栈为空时，将当前运算符入栈。
- 如果当前元素是左括号“（”，则直接入栈。
- 如果当前元素是右括号“）”，则依次弹出栈顶运算符加入后缀表达式中，直到遇到左括号为止，此时将左括号弹出，但不加入后缀表达式中。

### 1.6 后缀表达式求值

将后缀表达式求值的过程，也叫后缀表达式的求值。具体的求值规则如下：

- 遍历后缀表达式的每个元素。
- 如果当前元素是操作数，则将其入栈。
- 如果当前元素是运算符，则弹出栈顶的两个操作数，进行运算，并将运算结果入栈。
- 遍历完后缀表达式后，栈中只剩下一个元素，即为表达式的值。

## 2. 表达式求值的实现

### 2.1 中缀表达式转后缀表达式的实现

中缀表达式转后缀表达式可以使用栈来实现。具体的代码实现如下：

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

using namespace std;

// 判断一个字符是否为操作符
bool isOperator(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/';
}

// 判断两个操作符的优先级
int getPriority(char op1, char op2) {
    if ((op1 == '*' || op1 == '/') && (op2 == '+' || op2 == '-')) {
        return -1;
    } else if ((op1 == '+' || op1 == '-') && (op2 == '*' || op2 == '/')) {
        return 1;
    } else {
        return 0;
    }
}

// 将中缀表达式转换成后缀表达式
string infixToPostfix(string infix) {
    stack<char> opStack;  // 运算符栈
    string postfix;  // 后缀表达式

    for (char c : infix) {
        if (isdigit(c)) {  // 如果是数字，直接加入后缀表达式
            postfix += c;
        } else if (isOperator(c)) {  // 如果是操作符
            while (!opStack.empty() && opStack.top() != '(' && getPriority(opStack.top(), c) >= 0) {
                postfix += opStack.top();  // 弹出栈顶操作符加入后缀表达式
                opStack.pop();
            }
            opStack.push(c);
        } else if (c == '(') {  // 如果是左括号，直接入栈
            opStack.push(c);
        } else if (c == ')') {  // 如果是右括号
            while (!opStack.empty() && opStack.top() != '(') {
                postfix += opStack.top();  // 弹出栈顶操作符加入后缀表达式
                opStack.pop();
            }
            opStack.pop();  // 弹出左括号
        }
    }

    while (!opStack.empty()) {  // 将剩余的操作符加入后缀表达式
        postfix += opStack.top();
        opStack.pop();
    }

    return postfix;
}

int main() {
    string infix = "2+3*4-6/2";
    string postfix = infixToPostfix(infix);
    cout << postfix << endl;  // 输出后缀表达式：234*+62/-
    return 0;
}

### 2.2 后缀表达式求值的实现

后缀表达式求值也可以使用栈来实现。具体的代码实现如下：

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

using namespace std;

// 判断一个字符是否为操作符
bool isOperator(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/';
}

// 计算两个操作数的运算结果
int calculate(int a, int b, char op) {
    if (op == '+') {
        return a + b;
    } else if (op == '-') {
        return a - b;
    } else if (op == '*') {
        return a * b;
    } else {
        return a / b;
    }
}

// 计算后缀表达式的值
int evaluate(string postfix) {
    stack<int> numStack;  // 操作数栈

    for (char c : postfix) {
        if (isdigit(c)) {  // 如果是数字，将其转换成整数并入栈
            int num = c - '0';
            numStack.push(num);
        } else if (isOperator(c)) {  // 如果是操作符
            int b = numStack.top();
            numStack.pop();
            int a = numStack.top();
            numStack.pop();
            int result = calculate(a, b, c);
            numStack.push(result);
        }
    }

    return numStack.top();
}

int main() {
    string postfix = "234*+62/-";
    int result = evaluate(postfix);
    cout << result << endl;  // 输出计算结果：8
    return 0;
}

## 3. 总结

栈在表达式求值中的应用是很常见的，掌握了这个知识点，对于编写计算器等应用程序会有很大的帮助。