Java-学习记录：中缀表达式转后缀表达式
Martin7-1
2960
2021.08.31
发布于 未知归属地
Java中缀表达式后缀表达式学习分享

1 背景分析

表达式一共有前缀表达式(比较不常用)、中缀表达式(最为普及的)、后缀表达式三种方法，可以通过表达式树来构建三种不同的表达式，表达式树是一种二叉树，其构成是由操作数和操作符构成，其中叶子节点全部为操作数，其余节点为操作符。根据对其的遍历方法不同就会得到三种不同的表达式：

  1. 前序遍历：父节点永远会比子节点先遍历的一种遍历方法
  2. 中序遍历：
  3. 后序遍历：父节点永远比子节点后遍历的一种遍历方法

下面三幅图代表了我们在一课二叉树中是如何实现三种遍历的，请注意对应遍历方法的颜色。
(图片来自 南京大学2020届软件学院离散数学课程，若有侵权请联系删除)

image.png
image.png
image.png

For example:
转换为后缀表达式即为
6e138e506abff657d727b5d6abd83b6.png

其中，中缀表达式和后缀表达式是两种较为常见的表达式，使用后缀表达式的原因是我们不需要知道其中操作符的优先级顺序，也不需要括号来辅助。这两种表达式也是计算机学科中较为常用的表达式。从后缀表达式转为中缀表达式的方法较为简单，本篇不做讨论。本篇文章旨在分享如何从中缀表达式变为后缀表达式的算法思想。

2 算法简介

要将中缀表达式转换为后缀表达式，我们需要借助数据结构栈来处理，与此同时我们还需要一个地方来存储我们的输出（下面简称为输出）。然后我们根据以下的规则来遍历中缀表达式：

  1. 如果在中缀表达式中遇到 数字(或字母) 则直接输出该数字（或字母）。
  2. 如果遇到的是操作符，我们需要按照一定规则来将其进行入栈或者出栈操作：
    • 如果遇到的是右括号，则此时我们需要将栈中的元素逐一出栈，直到我们遇到了左括号，或者说我们遇到了对应的左括号。将右括号与左括号之间的操作符出栈且输出(注意我们并不会将括号输出，且此处地方需要将左括号也出栈)。
    • 如果遇到其他运算符(比如+、*、/等)，我们就从栈中弹出元素且输出直到遇到下一个优先级比当前要入栈的元素的优先级更低的操作符(除非遇到右括号，否则我们绝对不会弹出左括号)。当弹出例程完成后，我们再压入当前的操作符(即我们要保证压入操作符时，在栈的第二位的操作符的优先级是要低于栈顶的操作符的优先级的)
    • 遍历完整个中缀表达式后，如果栈并不是空的，我们就将栈中剩下的所有元素出栈输出。

在这个算法中，"("的优先级是最高的，其次是"*"、"/"，然后是"+"、"-"

3 Java语言实现具体算法

下面我们来看具体的算法

package nju.edu.com;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @algorithm 从中缀表达式变成后缀表达式
 * @author Zyi
 * @create 2021/8/31 22:50
 */
@SuppressWarnings("JavaDoc")
public class Transfer {

    /**
     * 用deque来模拟栈
     */
    private Deque<Character> stack = new LinkedList<>();

    public int getPriority(char character) {
        int priority = 0;

        switch (character) {
            case '+':
            case '-':
                priority = 2;
                break;
            case '*':
            case '/':
                priority = 3;
                break;
            case '(':
                priority = 4;
                break;
            case ')':
                priority = 5;
                break;
            default:
        }

        return priority;
    }

    public String transfer(String infix) {
        StringBuilder postfix = new StringBuilder();
        char[] characters = infix.toCharArray();

        for (char character : characters) {
            if (Character.isLetter(character) || Character.isDigit(character)) {
                postfix.append(character);
            } else {
                if (character == ')') {
                    while (stack.peek() != '(') {
                        postfix.append(stack.pop());
                    }
                    // 移除左括号
                    stack.pop();
                } else {
                    int currentPriority = getPriority(character);
                    while (true) {
                        if (stack.isEmpty()) {
                            stack.addFirst(character);
                            break;
                        } else {
                            if (getPriority(stack.peek()) >= currentPriority && stack.peek() != '(') {
                                postfix.append(stack.pop());
                            } else {
                                stack.addFirst(character);
                                break;
                            }
                        }
                    }
                }
            }
        }

        while (!stack.isEmpty()) {
            postfix.append(stack.pop());
        }

        return postfix.toString();
    }
}

算法分析：

  1. 用Java中的Deque双端队列来模拟栈，当然我们也可以选择数组、链表来模拟。
  2. getPriority(char character)用来获取当前操作符的优先级

4 总结

中缀表达式转后缀表达式可以说是栈的一种非常常见的应用。对我们理解栈这种结构有着很好的帮助。

评论 (2)