迭代法实现中缀表达式转后缀表达式

中缀表达式转后缀表达式的算法有两种，一种是使用栈的方法，另一种是使用迭代法。下面介绍一下迭代法实现中缀表达式转后缀表达式的步骤：

1. 创建一个空的输出队列和一个空的运算符栈。
2. 从左到右扫描中缀表达式。
3. 如果当前字符是操作数，则将其加入到输出队列中。
4. 如果当前字符是运算符，则进行如下操作：
a. 如果运算符栈为空，或者栈顶运算符为左括号"("，则将该运算符入栈。
b. 否则，若优先级比栈顶运算符的优先级高，也将运算符入栈。
c. 否则，将栈顶运算符弹出并加入到输出队列中，再次转到4.a与新的栈顶运算符比较。
5. 如果当前字符是左括号"("，则将其入栈。
6. 如果当前字符是右括号")"，则进行如下操作：
a. 重复弹出运算符并加入到输出队列中，直到遇到左括号为止。
b. 将左括号弹出，但不加入到输出队列中。
7. 重复步骤2至6，直到表达式的最右边。
8. 将运算符栈中剩余的运算符依次弹出并加入到输出队列中。
9. 输出队列中的元素即为后缀表达式。

相关问题

实现对输入的中缀表达式、前缀表达式、后缀表达式分别求值

### 中缀表达式、前缀表达式和后缀表达式的求值

对于中缀表达式、前缀表达式以及后缀表达式的求值，可以采用不同的策略。针对每种类型的表达式，存在特定的方法来进行解析和计算。

#### 中缀表达式的求值

由于直接评估中缀表达式较为复杂，通常先将其转换成更容易处理的形式——如后缀表达式（也称为逆波兰表示），再进行求值。此过程涉及到了调度场算法的应用[^1]：

def infix_to_postfix(expression):
    precedence = {'+':1, '-':1, '*':2, '/':2}
    stack = []  # only pop when encounter an operator or end of expression
    output = []
    tokens = expression.split()

    for token in tokens:
        if token.isnumeric():
            output.append(token)
        elif token == '(':
            stack.append(token)
        elif token == ')':
            top_token = stack.pop()
            while top_token != '(':
                output += top_token,
                top_token = stack.pop()
        else:
            while (stack and stack[-1]]):
                output += stack.pop(),
            stack.append(token)

    while stack:
         output += stack.pop(),

    return " ".join(output)


def evaluate_postfix(postfix_expr):
    operand_stack = []

    for token in postfix_expr.split():
        if token.isdigit():
            operand_stack.append(int(token))
        else:
            op2 = operand_stack.pop()
            op1 = operand_stack.pop()
            result = do_math(op1, op2, token)
            operand_stack.append(result)

    return operand_stack.pop()


def do_math(operand1, operand2, operator):
    if operator == "*":
        return operand1 * operand2
    elif operator == "/":
        return operand1 / operand2
    elif operator == "+":
        return operand1 + operand2
    else:
        return operand1 - operand2


infix_expression = '7 + 3 * (4 - 2)'
postfix_expression = infix_to_postfix(infix_expression.replace(' ', ''))

print(f'Postfix Expression: {postfix_expression}')
result = evaluate_postfix(postfix_expression)
print(f'Result: {result}')  

上述代码展示了如何通过Python实现从给定的中缀表达式`7 + 3 * (4 - 2)`转化为对应的后缀形式并最终得到其数值结果的过程。

#### 前缀表达式的求值

前缀表达式的求值可以通过递归的方式解决，在遇到操作数时压入栈内；当碰到运算符，则弹出相应数量的操作数执行对应运算，并把结果重新推回栈顶作为新的操作数继续参与后续可能存在的其他运算之中。

def prefix_evaluation(prefix_exp_str):
    operators = set(['+', '-', '*', '/', '^'])
    stack = []

    elements_list = prefix_exp_str.strip().split()[::-1]

    for element in elements_list:

        if element not in operators:
            try:
                stack.append(float(element))
            except ValueError:
                raise ValueError("Invalid Prefix Expression")

        else:
            str1 = stack.pop()
            str2 = stack.pop()

            res = apply_operation(str1,str2,element)
            stack.append(res)
    
    return stack.pop() 

def apply_operation(a,b,operator):
    match operator:
        case '+':
            return a+b
        case '-':
            return b-a
        case '*':
            return a*b
        case '/':
            return b/a
        case '^':
            return pow(b,a)
        
prefix_expression = "- + * 8 9 / 6 3"
evaluated_result = prefix_evaluation(prefix_expression)
print(f"The evaluated value is :{evaluated_result}")

这段程序实现了从前缀字符串读取输入直到返回最后的结果整个流程[^2]。

#### 后缀表达式的求值

后缀表达式的求值相对简单得多，因为不需要考虑括号优先级等问题。只需要按照顺序扫描每一个token，若是数字就存入堆栈里等待进一步处理；一旦发现是算术符号就可以立即取出最近两次存储的数据做相应的四则运算并将所得答案再次放入堆栈顶部准备下一轮迭代使用。

from collections import deque

def evalRPN(tokens):

    operations = {
        "+": lambda a, b: a + b,
        "-": lambda a, b: b - a,
        "*": lambda a, b: a * b,
        "/": lambda a, b: int(b / a),
    }

    nums = deque([])

    for i in range(len(tokens)):
        numOrOp = tokens[i]
        if numOrOp.lstrip('-').isdigit():   
            nums.appendleft(int(numOrOp))     
        else:
            operation = operations[numOrOp]
            firstNum = nums.popleft()
            secondNum = nums.popleft()
            newNumber = operation(firstNum,secondNum)
            nums.appendleft(newNumber)

    return nums[0]


rpn_tokens = ["2", "1", "+", "3", "*"]
evaluation_outcome = evalRPN(rpn_tokens)
print(f"Evaluation outcome:{evaluation_outcome}")  

该片段提供了一个简洁明了的例子说明怎样利用队列结构高效地完成对逆波兰记法所描述公式的即时演算工作。

实验题⽬3： 中缀表达式转后缀表达式 任务： 使⽤栈来将中缀表达式转换为后缀表达式。 实现步骤： 遍历中缀表达式： 遇到操作数直接添加到结果中，遇到操作符时，根据优先级处理栈中的操作符。 处理栈： 在遍历结束后，将栈中剩余的操作符添加到结果中。使用Java写出代码

实验题目3的目标是将中缀表达式转化为后缀表达式，也称为逆波兰表示法（Reverse Polish Notation，RPN）。这个过程利用了栈的数据结构特性。以下是基本的实现步骤：

1. 初始化一个空栈和一个空的结果列表（或字符串）。
2. 遍历输入的中缀表达式的每个字符：
- 如果字符是一个操作数，将其直接追加到结果列表中。
- 如果字符是一个运算符，检查栈顶元素是否也是一个运算符。如果是且优先级低于当前运算符，则把栈顶元素压入结果列表，然后继续检查下一个栈顶元素，直到找到一个比当前运算符低优先级或者栈为空。如果栈顶元素的优先级高于或等于当前运算符，那么就直接把当前运算符压入栈中。
3. 遍历完成后，栈里剩下的都是运算符，依次将其压入结果列表。
4. 最终得到的结果列表就是后缀表达式。

在Java中，你可以创建一个递归版本或者迭代版本的函数来完成这个任务。这里提供一个简单的非递归版本的示例代码：

import java.util.Stack;

public class InfixToPostfix {
    public static String infixToPostfix(String expression) {
        Stack<Character> stack = new Stack<>();
        StringBuilder postfixBuilder = new StringBuilder();
        for (char c : expression.toCharArray()) {
            if (Character.isDigit(c)) { // 操作数
                postfixBuilder.append(c);
            } else if (c == '+' || c == '-' || c == '*' || c == '/') { // 运算符
                while (!stack.isEmpty() && precedence(stack.peek()) >= precedence(c)) {
                    postfixBuilder.append(stack.pop());
                }
                stack.push(c);
            }
        }
        while (!stack.isEmpty()) { // 将剩余栈顶的运算符添加到后缀表达式
            postfixBuilder.append(stack.pop());
        }
        return postfixBuilder.toString();
}

private static int precedence(char op) {
    switch (op) {
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        default:
            throw new IllegalArgumentException("Invalid operator");
    }
}