04.3 中缀转后缀

2024 年 7 月 18 日 星期四(已编辑)
这篇文章上次修改于 2024 年 7 月 19 日 星期五,可能部分内容已经不适用,如有疑问可询问作者。

04.3 中缀转后缀

中缀表达式转后缀表达式与栈的妙用

1. 中缀表达式与后缀表达式

1.1 中缀表达式的特点

中缀表达式是日常最常见的数学表达形式,其中运算符位于两个操作数之间,例如:3 + 4 * 5

1.2 后缀表达式的特点

后缀表达式是将运算符置于操作数之后的形式,例如:3 4 5 * +

2. 中缀表达式转后缀表达式

2.1 转换规则

中缀表达式转后缀表达式的转换规则如下:

  1. 从左至右遍历中缀表达式的每个元素。
  2. 如果是操作数,直接输出到后缀表达式。
  3. 如果是运算符:
    • 如果栈为空,或者栈顶元素是左括号 "(",直接将运算符压入栈。
    • 如果运算符优先级高于栈顶运算符,直接将运算符压入栈。
    • 否则,将栈顶运算符弹出并输出到后缀表达式,然后重复比较直到满足前两个条件。
  4. 如果是左括号 "(",将其压入栈。
  5. 如果是右括号 ")",将栈中的运算符依次弹出并输出到后缀表达式,直到遇到左括号 "("。
1) 初始化两个栈:运算符栈s1和储存中间结果的栈s2;
2) 从左至右扫描中缀表达式;
3) 遇到操作数时,将其压s2;
4) 遇到运算符时,比较其与s1栈顶运算符的优先级:
1.如果s1为空,或栈顶运算符为左括号“(”,则直接将此运算符入栈;
2.否则,若优先级比栈顶运算符的高,也将运算符压入s1;
3.否则,将s1栈顶的运算符弹出并压入到s2中,再次转到(4.1)与s1中新的栈顶运算符相比较;
5) 遇到括号时:
(1) 如果是左括号“(”,则直接压入s1  
(2) 如果是右括号“)”,则依次弹出s1栈顶的运算符,并压入s2,直到遇到左括号为止,此时将这一对括号丢弃
6) 重复步骤2至5,直到表达式的最右边
7) 将s1中剩余的运算符依次弹出并压入s2
8)  依次弹出s2中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式

2.2 转换实例

以中缀表达式 3 + 4 * 5 为例,转换过程如下:

1. 输入:3 + 4 * 5
2. 输出:3 4 5 * +

3. 利用栈求值后缀表达式

3.1 求值规则

利用栈求值后缀表达式的规则如下:

  1. 从左至右遍历后缀表达式的每个元素。
  2. 如果是操作数,压入栈。
  3. 如果是运算符,从栈中弹出两个操作数,进行运算,并将结果压入栈。

3.2 求值实例

以后缀表达式 3 4 5 * + 为例,求值过程如下:

1. 输入:3 4 5 * +
2. 栈操作:
   - 遇到 3,压入栈: [3]
   - 遇到 4,压入栈: [3, 4]
   - 遇到 5,压入栈: [3, 4, 5]
   - 遇到 *,弹出 5 和 4,计算结果 20,压入栈: [3, 20]
   - 遇到 +,弹出 20 和 3,计算结果 23,压入栈: [23]
3. 最终结果:23

4. 示例:Python 实现中缀转后缀与求值

class Stack:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return len(self.items) == 0

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()

    def peek(self):
        if not self.is_empty():
            return self.items[-1]

    def size(self):
        return len(self.items)

def infix_to_postfix(infix_expr):
    stack = Stack()
    postfix_expr = []
    operators = {'+': 1, '-': 1, '*': 2, '/': 2, '(': 0}

    for token in infix_expr.split():
        if token.isdigit():
            postfix_expr.append(token)
        elif token == '(':
            stack.push(token)
        elif token == ')':
            while stack.peek() != '(':
                postfix_expr.append(stack.pop())
            stack.pop()  # 弹出左括号
        elif token in operators:
            while stack.size()

 > 0 and operators[token] <= operators.get(stack.peek(), 0):
                postfix_expr.append(stack.pop())
            stack.push(token)

    while not stack.is_empty():
        postfix_expr.append(stack.pop())

    return ' '.join(postfix_expr)

def evaluate_postfix(postfix_expr):
    stack = Stack()
    operators = set(['+', '-', '*', '/'])

    tokens = postfix_expr.split()
    for token in tokens:
        if token.isdigit():
            stack.push(int(token))
        elif token in operators:
            operand2 = stack.pop()
            operand1 = stack.pop()
            if token == '+':
                stack.push(operand1 + operand2)
            elif token == '-':
                stack.push(operand1 - operand2)
            elif token == '*':
                stack.push(operand1 * operand2)
            elif token == '/':
                stack.push(operand1 / operand2)

    return stack.pop()

# 示例
infix_expression = "3 + 4 * 5"
postfix_expression = infix_to_postfix(infix_expression)
result = evaluate_postfix(postfix_expression)
print(f"中缀表达式:{infix_expression}")
print(f"后缀表达式:{postfix_expression}")
print(f"求值结果:{result}")

4. 示例:Java 实现中缀转后缀与求值

package org.example;  
  
import java.util.ArrayList;  
import java.util.List;  
import java.util.Objects;  
import java.util.Stack;  
import java.util.stream.Collectors;  
  
public class PolandNotation {  
  
//    1 + ( ( 2 + 3 )× 4) - 5转成中缀表达式,对字符串操作麻烦,所以先转成list  
    //操作list,转成后缀表达式  
  
  
    public static void main(String[] args) {  
  
        String expression = "1+((2+3)*4)-5";  
        System.out.println("中缀表达式是:" + toInfixExpressionList(expression));  
        System.out.println("后缀表达式是:" + parseSuffixExpressionList(toInfixExpressionList(expression)));  
  
        System.out.println("expression = " + calculate(parseSuffixExpressionList(toInfixExpressionList(expression))));  
        //定义逆波兰表达式(3+4)*5-6  3 4 + 5 * 6 -  
        String suffixExpression = "3 4 + 5 * 6 - ";  
        // suffixExpression放入arraylist中  
        // suffixExpression传递给一个方法,遍历ArrayList,配合栈,完成计算  
        List<String> rpnList = getListString(suffixExpression);  
        System.out.println("rpnlist = " + rpnList);  
  
        int res = calculate(rpnList);  
        System.out.println(res);  
    }  
  
    public static List<String> parseSuffixExpressionList(List<String> ls) {  
        Stack<String> s1 = new Stack<String>();  
//        Stack<String> s2 = new Stack<String>();//保存中间结果  
  
        List<String> s2 = new ArrayList<String>();  
//        遍历ls,  
        for (String item : ls) {  
            if (item.matches("\\d+")) {  
                s2.add(item);  
            } else if (item.equals("(")) {  
                s1.push(item);  
            } else if (item.equals(")")) {  
                while (!s1.peek().equals("(")) {  
                    s2.add(s1.pop());  
  
                }  
                s1.pop();//消除括号  
            } else {  
                //当item的运算符优先级小于等于s1栈顶运算符优先级,  
                //s1栈顶运算符弹栈 压入s2中,  
                while (s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)) {  
                    s2.add(s1.pop());  
                }  
                s1.push(item);  
            }  
        }  
//        将s1中剩余的运算符依次弹出并压入s2  
        while (s1.size() != 0) {  
            s2.add(s1.pop());  
        }  
  
        return s2;  
    }  
  
    public static List<String> toInfixExpressionList(String s) {  
        ArrayList<String> ls = new ArrayList<String>();  
        int i = 0;//用于遍历s  
        String str1;//对多位数进行拼接  
        char c;//每遍历一个字符就放入c  
        do {  
            if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {//非数字  
                ls.add("" + c);  
                i++;  
            } else {  
                //是数字,考虑多位数,需要拼接  
                str1 = "";  
                while (i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) {  
                    //取出的仍然是数字  
                    str1 += c;  
                    i++;  
                }  
                ls.add(str1);  
            }  
        } while (i < s.length());  
//        for(String item :ls){  
//            if (item.equals(" ")){  
//                ls.remove(item);  
//            }  
//        }  
//        ls.removeIf(str -> str.isEmpty());  
//        ls.stream().map(s -> s.replaceAll("\n",",").trim()).collect(Collectors.toList());  
//        ls.stream().map(s1 -> s1.replaceAll("\n", ",").trim()).collect(Collectors.toList());  
        return ls;  
    }  
  
    //将逆波兰表达式,依次将数字和运算符放入Array List中  
    public static List<String> getListString(String suffixExpression) {  
        //分割suffixExpression  
        String[] s = suffixExpression.split(" ");  
        ArrayList<String> list = new ArrayList<>();  
        for (String ele : s) {  
            list.add(ele);  
        }  
        return list;  
    }  
  
    public static int calculate(List<String> ls) {  
        //创建一个栈  
        Stack<String> stack = new Stack<>();  
        // 遍历ls  
        for (String item : ls) {  
            // 正则表达式取数  
            if (item.matches("\\d+")) {  
                stack.push(item);  
            } else {  
                int num1 = Integer.parseInt(stack.pop());  
                int num2 = Integer.parseInt(stack.pop());  
                int res;  
                if (item.equals("+")) {  
                    res = num1 + num2;  
                } else if (item.equals("-")) {  
                    res = num2 - num1;  
                } else if (item.equals("*")) {  
                    res = num2 * num1;  
                } else if (item.equals("/")) {  
                    res = num1 / num2;  
                } else {  
                    throw new RuntimeException("运算符有误");  
                }  
                stack.push(res + "");  
            }  
        }  
        return Integer.parseInt(stack.pop());  
    }  
}  
  
//返回运算符对应的优先级  
class Operation {  
    public static int ADD = 1;  
    public static int SUB = 1;  
    public static int MUL = 2;  
    public static int DIV = 2;  
  
    public static int getValue(String operation) {  
        int result = 0;  
        switch (operation) {  
            case "+":  
                result = ADD;  
                break;  
            case "-":  
                result = SUB;  
                break;  
            case "*":  
                result = MUL;  
                break;  
            case "/":  
                result = DIV;  
                break;  
            default:  
//                throw new RuntimeException("不存在");  
                System.out.println("不存在");  
                break;  
        }  
        return result;  
    }  
}

5. 总结

通过栈的巧妙运用,可以高效地将中缀表达式转换为后缀表达式,并在后缀表达式上进行求值。这种方法简化了表达式的处理逻辑,使得程序更容易理解和实现。

  • Loading...
  • Loading...
  • Loading...
  • Loading...
  • Loading...