讲义

表达式转换

2024/8/3

# 一、表达式的基本概念

在计算机科学中，表达式是用来计算值的语句。表达式可以用不同的表示法进行书写，每种表示法在处理计算和编译时有不同的作用。以下是三种主要的表达式表示法：

  1. 中缀表达式 (Infix Expression)

    • 操作符位于操作数之间。
    • 示例：A + B，3 * (4 + 5)。
    • 中缀表达式是我们最常见的数学表达式形式，它在数学和计算中广泛使用。

  2. 前缀表达式 (Prefix Expression)

    • 操作符位于操作数之前。
    • 示例：+ A B，* 3 + 4 5。
    • 前缀表达式也被称为波兰表示法，不需要括号来确定操作顺序，这使得它在计算机处理中非常高效。

  3. 后缀表达式 (Postfix Expression)

    • 操作符位于操作数之后。
    • 示例：A B +，3 4 5 + *。
    • 后缀表达式也称为逆波兰表示法，它同样不需要括号来确定操作顺序，便于计算机程序进行计算。

# 二、表达式树

表达式树是一种用于表示算术表达式的树形结构。每个内部节点表示一个操作符，每个叶子节点表示一个操作数。

# 1. 表达式树的构建

表达式树构建步骤：

  • 将表达式转换为树的结构，其中每个操作符成为树的一个内部节点，每个操作数成为树的一个叶子节点。
  • 确保操作符和操作数的位置正确以反映原始表达式的结构。

示例： 对于表达式 a * (b - c) / (d + e)，其表达式树如下：

       /
     *   +
   a   - d e
       b c

# 2. 表达式树的遍历

表达式树可以通过三种主要的遍历方法来访问节点，分别对应于不同的表达式表示法：

  • 先序遍历 (Preorder Traversal)

    • 访问根节点
    • 遍历左子树
    • 遍历右子树
    • 对应前缀表达式（Prefix Expression）

  • 中序遍历 (Inorder Traversal)

    • 遍历左子树
    • 访问根节点
    • 遍历右子树
    • 对应中缀表达式（Infix Expression）

  • 后序遍历 (Postorder Traversal)

    • 遍历左子树
    • 遍历右子树
    • 访问根节点
    • 对应后缀表达式（Postfix Expression）

示例代码：

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

struct Node {
    char value;
    Node* left;
    Node* right;
    Node(char v) : value(v), left(nullptr), right(nullptr) {}
};

// 先序遍历
void preorder(Node* node) {
    if (node == nullptr) return;
    cout << node->value;
    preorder(node->left);
    preorder(node->right);
}

// 中序遍历
void inorder(Node* node) {
    if (node == nullptr) return;
    inorder(node->left);
    cout << node->value;
    inorder(node->right);
}

// 后序遍历
void postorder(Node* node) {
    if (node == nullptr) return;
    postorder(node->left);
    postorder(node->right);
    cout << node->value;
}

int main() {
    // 构建表达式树 a * (b - c) / (d + e)
    Node* root = new Node('/');
    root->left = new Node('*');
    root->left->left = new Node('a');
    root->left->right = new Node('-');
    root->left->right->left = new Node('b');
    root->left->right->right = new Node('c');
    root->right = new Node('+');
    root->right->left = new Node('d');
    root->right->right = new Node('e');

    cout << "先序遍历（前缀表示）: ";
    preorder(root);
    cout << endl;

    cout << "中序遍历（中缀表示）: ";
    inorder(root);
    cout << endl;

    cout << "后序遍历（后缀表示）: ";
    postorder(root);
    cout << endl;

    // 释放内存
    delete root->left->right->left;
    delete root->left->right->right;
    delete root->left->right;
    delete root->left->left;
    delete root->left;
    delete root->right->left;
    delete root->right->right;
    delete root->right;
    delete root;

    return 0;
}

# 三、表达式转换

# 1. 中缀表达式到后缀表达式

  1. 方法一：加括号法/直接法
  • 注意每一个配对的括号内都包含两个子表达式和一个运算符
  • 示例:中缀表达式 (a+b)*c+d-(e+g)*h 转换为后缀表达式 ab+c*d+eg+h*-
  • 第一步：使用加括号法按照算数优先级将中缀表达式添加括号 ((((a+b)*c)+d)-((e+g)*h))
  • 第二步：将同一括号内的运算符提取到括号后面，得到 ((((ab)+c)*d)+((eg)+h)*)-
  • 第三步：去掉括号，得到后缀表达式 ab+c*d+eg+h*-
  1. 方法二：遍历树法
  • 使用树的中序遍历和后序遍历来实现中缀表达式到后缀表达式的转换
  • 示例:中缀表达式 (a+b)*c+d-(e+g)*h 转换为树形结构如下：
        -
      /   \
     +     *
    / \   / \
    *  d  +  h
   / \   / \
   +  c e   g
  / \
 a   b
  • 中序遍历：a+b*c+d-e+g*h
  • 后序遍历：ab+c*d+eg+h*-
  1. 方法二：栈法

使用栈法来将中缀表达式转换为后缀表达式是常见且高效的方法。基本思想是利用栈来暂存操作符，并根据操作符的优先级和括号的匹配来控制操作符出栈的时机。

步骤说明：

  1. 初始化一个空栈S，用于存放操作符，初始化一个空的结果字符串R，用于存放最后的后缀表达式。
  2. 从左到右扫描中缀表达式的每一个字符。
    • 如果遇到操作数（如操作数a，b），直接添加到结果字符串R中。
    • 如果遇到操作符+, -, *, /，则根据以下规则处理：
      • 如果栈S为空或栈顶为左括号(，则直接将操作符压入栈S。
      • 否则，比较当前操作符与栈顶操作符的优先级，如果当前操作符优先级较高，将其压入栈S；否则，弹出栈顶操作符并添加到结果字符串R中，重复此步骤直到栈为空或栈顶操作符优先级低于当前操作符，再将当前操作符压入栈S。
    • 如果遇到左括号(，将其压入栈S。
    • 如果遇到右括号)，则依次弹出栈顶操作符并添加到结果字符串R中，直到遇到左括号(，将左括号丢弃。
  3. 扫描完成后，如果栈S中仍有操作符，则依次弹出并添加到结果字符串R中。
  4. 最终结果字符串R就是对应的后缀表达式。

示例:
将中缀表达式 (a+b)*c+d-(e+g)*h 转换为后缀表达式：

  • 扫描(，栈：(，结果：``
  • 扫描a，栈：(，结果：a
  • 扫描+，栈：( +，结果：a
  • 扫描b，栈：( +，结果：ab
  • 扫描)，栈：( + -> ( -> 栈为空，结果：ab+
  • 扫描*，栈：*，结果：ab+
  • 扫描c，栈：*，结果：ab+c
  • 扫描+，栈：+ -> *出栈，结果：ab+c* -> +入栈，栈：+
  • 扫描d，栈：+，结果：ab+c*d
  • 扫描-，栈：- -> +出栈，结果：ab+c*d+ -> -入栈，栈：-
  • 扫描(，栈：- (，结果：ab+c*d+
  • 扫描e，栈：- (，结果：ab+c*d+e
  • 扫描+，栈：- ( +，结果：ab+c*d+e
  • 扫描g，栈：- ( +，结果：ab+c*d+eg
  • 扫描)，栈：- ( + -> ( -> 栈-，结果：ab+c*d+eg+
  • 扫描*，栈：- *，结果：ab+c*d+eg+
  • 扫描h，栈：- *，结果：ab+c*d+eg+h
  • 扫描完成，栈- *出栈 -> 结果：ab+c*d+eg+h*-

最终得到后缀表达式：ab+c*d+eg+h*-

# 2. 中缀表达式到前缀表达式

  1. 方法一：加括号法/直接法
  • 注意每一个配对的括号内都包含两个子表达式和一个运算符
  • 示例:中缀表达式 (a+b)*c+d-(e+g)*h 转换为前缀表达式 -+*+abcd*+egh
  • 第一步：使用加括号法按照算数优先级将中缀表达式添加括号 ((((a+b)*c)+d)-((e+g)*h))
  • 第二步：将同一括号内的运算符提取到括号前面，得到 -(+(*(+(ab)c)d)*(+(eg)h))
  • 第三步：去掉括号，得到前缀表达式 -+*+abcd*+egh
  1. 方法二：遍历树法
  • 使用树的中序遍历和前序遍历来实现中缀表达式到前缀表达式的转换
  • 示例:中缀表达式 (a+b)*c+d-(e+g)*h 转换为树形结构如下：
        -
      /   \
     +     *
    / \   / \
    *  d  +  h
   / \   / \
   +  c e   g
  / \
 a   b
  • 中序遍历：a+b*c+d-e+g*h
  • 前序遍历：-+*+abcd*+egh
  1. 方法二：栈法

栈法也可以用于将中缀表达式转换为前缀表达式。基本步骤与转换为后缀表达式类似，只是操作顺序和处理方式略有不同。

步骤说明：

  1. 首先将中缀表达式进行反转，即将表达式的顺序倒置，并将左右括号互换。
  2. 然后，按照将中缀表达式转换为后缀表达式的规则，将反转后的中缀表达式转换为后缀表达式。
  3. 最后，将所得的后缀表达式再次反转，得到的结果就是对应的前缀表达式。

示例:
将中缀表达式 (a+b)*c+d-(e+g)*h 转换为前缀表达式：

  • 反转表达式：h*(g+e)-d+c*(b+a)
  • 将反转后的中缀转换为后缀：
    • 扫描h，结果：h
    • 扫描*，结果：h
    • 扫描(，栈：(，结果：h
    • 扫描g，结果：hg
    • 扫描+，栈：( +，结果：hg
    • 扫描e，结果：hge
    • 扫描)，栈：+ -> 出栈 -> 结果：hge+
    • 扫描-，栈：-，结果：hge+*
    • 扫描d，结果：hge+*d
    • 扫描+，栈：+，结果：hge+*d-
    • 扫描c，结果：hge+*d-c
    • 扫描*，栈：*，结果：hge+*d-c
    • 扫描(，栈：( *，结果：hge+*d-c
    • 扫描b，结果：hge+*d-cb
    • 扫描+，栈：( * +，结果：hge+*d-cb
    • 扫描a，结果：hge+*d-cba
    • 扫描)，栈：+ -> 出栈 -> 结果：hge+*d-cba+*
  • 得到后缀表达式：hge+*d-cba+*
  • 反转后缀表达式：-*+abc+d*+egh

最终得到前缀表达式：-+*+abcd*+egh

# 3. 后缀表达式到中缀表达式

  1. 方法一：加括号法/直接法
  • 遇到连续两个表达式加一个运算符的组合,即将其转换为中缀, 运算流程如下:
  • 示例:后缀表达式 ab+c*d+eg+h*-转换为中缀表达式 (a+b)*c+d-(e+g)*h
  • (a+b)c*d+eg+h*-
  • ((a+b)*c)d+eg+h*-
  • (((a+b)*c)+d)eg+h*-
  • (((a+b)*c)+d)(e+g)h*-
  • (((a+b)*c)+d)((e+g)*h)-
  • ((((a+b)*c)+d)-((e+g)*h))
  • (a+b)*c+d-(e+g)*h
  1. 方法二：栈法

使用栈法可以高效地将后缀表达式转换为中缀表达式。栈法的基本思想是将操作数逐个入栈，遇到操作符时，弹出两个操作数并构建一个中缀子表达式，然后将该子表达式再压回栈中。

步骤说明：

  1. 初始化一个空栈S。
  2. 从左到右扫描后缀表达式的每一个字符。
    • 如果是操作数，将其压入栈S。
    • 如果是操作符，弹出栈顶的两个操作数，构建一个中缀表达式（如a op b），并将该中缀表达式的结果压入栈S。
  3. 扫描结束后，栈顶元素即为最终的中缀表达式。

示例: 将后缀表达式 ab+c*d+eg+h*- 转换为中缀表达式：

  • 扫描a，栈：a
  • 扫描b，栈：a b
  • 扫描+，栈：(a+b)
  • 扫描c，栈：(a+b) c
  • 扫描*，栈：((a+b)*c)
  • 扫描d，栈：((a+b)*c) d
  • 扫描+，栈：(((a+b)*c)+d)
  • 扫描e，栈：(((a+b)*c)+d) e
  • 扫描g，栈：`(((a+b)*

c)+d) e g`

  • 扫描+，栈：(((a+b)*c)+d) (e+g)
  • 扫描h，栈：(((a+b)*c)+d) (e+g) h
  • 扫描*，栈：(((a+b)*c)+d) ((e+g)*h)
  • 扫描-，栈：((((a+b)*c)+d)-((e+g)*h))

最终得到中缀表达式：(a+b)*c+d-(e+g)*h

# 4. 前缀表达式到中缀表达式

  1. 方法一：加括号法/直接法
  • 遇到连续两个表达式加一个运算符的组合,即将其转换为中缀, 运算流程如下:
  • 示例:前缀表达式 -+*+abcd*+egh转换为中缀表达式 (a+b)*c+d-(e+g)*h
  • -+*+abcd*+egh
  • -+*(a+b)cd*(e+g)h
  • -+((a+b)*c)d((e+g)*h)
  • -(((a+b)*c)+d)((e+g)*h)
  • (((a+b)*c)+d)-((e+g)*h)
  • (a+b)*c+d-(e+g)*h
  1. 方法二：栈法

栈法也可以用于将前缀表达式转换为中缀表达式，步骤与后缀转中缀类似，但需要从右向左扫描表达式。

步骤说明：

  1. 初始化一个空栈S。
  2. 从右到左扫描前缀表达式的每一个字符。
    • 如果是操作数，将其压入栈S。
    • 如果是操作符，弹出栈顶的两个操作数，构建一个中缀表达式（如a op b），并将该中缀表达式的结果压入栈S。
  3. 扫描结束后，栈顶元素即为最终的中缀表达式。

示例: 将前缀表达式 -+*+abcd*+egh 转换为中缀表达式：

  • 扫描h，栈：h
  • 扫描g，栈：g h
  • 扫描+，栈：(g+h)
  • 扫描e，栈：e (g+h)
  • 扫描*，栈：(e*(g+h))
  • 扫描d，栈：d (e*(g+h))
  • 扫描c，栈：c d (e*(g+h))
  • 扫描+，栈：(c+d) (e*(g+h))
  • 扫描b，栈：b (c+d) (e*(g+h))
  • 扫描a，栈：a b (c+d) (e*(g+h))
  • 扫描+，栈：(a+b) (c+d) (e*(g+h))
  • 扫描*，栈：((a+b)*c) (e*(g+h))
  • 扫描+，栈：(((a+b)*c)+d) (e*(g+h))
  • 扫描-，栈：((((a+b)*c)+d)-((e*(g+h))))

最终得到中缀表达式：(a+b)*c+d-(e+g)*h

# 5. 后缀表达式到前缀表达式

# 6. 前缀表达式到后缀表达式

以上两种转换方法可以通过先将表达式转换为中缀表达式，再将中缀表达式转换为所需表达式的方法来实现。

# 为什么在中缀表达式转换为其他形式时有建议使用遍历树法，而在其他形式转换为中缀时较少推荐这种方法的原因：

# 中缀转其他（前缀或后缀）：

  1. 复杂的操作符优先级：中缀表达式的操作符顺序和优先级比其他表达式更复杂，因此通过构建表达式树（AST），你可以很好地捕捉操作符的优先级和表达式的结构。然后通过遍历树（前序遍历、后序遍历）可以直接得到对应的前缀或后缀表达式。

  2. 树结构天然适应中缀表达式：中缀表达式在树结构中自然对应着二叉树的结构，根节点为操作符，左右子树为操作数或子表达式。通过这种结构很容易生成前缀或后缀表达式。

# 其他转中缀：

  1. 前缀/后缀的操作符顺序明确：前缀和后缀表达式的操作符顺序已经非常明确，因此不需要通过表达式树的方式来调整操作符优先级。在转换为中缀时，通常通过栈结构就能有效地处理。

  2. 直接解析：因为前缀和后缀表达式在解析时，已经按照运算符和操作数的顺序排列好，因此可以直接通过栈的方式逐步解析并构建出中缀表达式，而无需建立复杂的树结构。

# 小结

  • 中缀到其他表达式：由于中缀表达式本身的复杂性和操作符优先级问题，使用遍历树法能够更好地捕捉表达式的结构和顺序。
  • 其他表达式到中缀：由于前缀和后缀表达式的顺序已固定，转换时不需要额外的结构来处理优先级问题，栈结构足以完成任务，因此遍历树法显得过于复杂且不必要。
上次更新: 2024-10-19 10:01:51

哈夫曼编码