题目描述补充

题目：将表达式转换为波兰表达式（也称为前缀表达式）

波兰表达式是一种数学表达式的表示方法，其中运算符位于其操作数之前。例如，算术表达式 (3 + 4) * 2 转换为波兰表达式为 * + 3 4 2。请编写一个函数，该函数接收一个包含数字和运算符（+, -, *, /）的中缀表达式字符串作为输入，并返回其对应的波兰表达式字符串。

注意：

1. 输入的中缀表达式是有效的，即括号正确匹配，运算符仅包含 +, -, *, /，操作数仅包含非负整数。
2. 假设除法总是整数除法。

示例代码

PHP 示例

function infixToPrefix($expression) {
    $stack = [];
    $tokens = strtok($expression, ' +-*/()');
    
    while ($tokens !== false) {
        $token = $tokens;
        $tokens = strtok(' +-*/()');

        if ($token === '') continue;

        if (is_numeric($token)) {
            // 操作数直接输出
            $output = $token . ' ' . $output;
        } elseif ($token === '(') {
            // 左括号压入栈
            array_push($stack, $token);
        } elseif ($token === ')') {
            // 遇到右括号，弹出栈内元素并构建波兰表达式
            $prefix = '';
            while (end($stack) !== '(') {
                $prefix = array_pop($stack) . ' ' . $prefix;
            }
            array_pop($stack); // 弹出 '('
            $output = $prefix . ' ' . $output;
        } else {
            // 运算符，弹出栈顶运算符直到遇到左括号或更高优先级的运算符
            while (!empty($stack) && getOperatorPriority($stack[count($stack) - 1]) >= getOperatorPriority($token)) {
                $output = array_pop($stack) . ' ' . $output;
            }
            array_push($stack, $token);
        }
    }

    // 弹出栈中剩余的运算符
    while (!empty($stack)) {
        $output = array_pop($stack) . ' ' . $output;
    }

    // 去除多余的空格并返回
    return trim($output);
}

function getOperatorPriority($op) {
    if ($op === '+' || $op === '-') return 1;
    if ($op === '*' || $op === '/') return 2;
    return 0;
}

// 示例
echo infixToPrefix("(3 + 4) * 2"); // 输出: * + 3 4 2

Python 示例

def infixToPrefix(expression):
    stack = []
    output = []

    def precedence(op):
        if op in ('+', '-'):
            return 1
        if op in ('*', '/'):
            return 2
        return 0

    for char in expression:
        if char.isdigit():
            # 处理多位数
            num = ''
            while char.isdigit():
                num += char
                char = expression[expression.index(char) + 1] if char in expression else ''
            output.append(num)
            continue

        if char == '(':
            stack.append(char)
        elif char == ')':
            while stack and stack[-1] != '(':
                output.append(stack.pop())
            stack.pop()  # Pop '('
        else:
            while stack and precedence(stack[-1]) >= precedence(char):
                output.append(stack.pop())
            stack.append(char)

    while stack:
        output.append(stack.pop())

    return ' '.join(output[::-1])

# 示例
print(infixToPrefix("(3 + 4) * 2"))  # 输出: * + 3 4 2

JavaScript 示例

function infixToPrefix(expression) {
    let stack = [];
    let output = [];

    const precedence = (op) => {
        if (op === '+' || op === '-') return 1;
        if (op === '*' || op === '/') return 2;
        return 0;
    };

    let token = '';
    for (let char of expression) {
        if (!isNaN(char)) {
            // 处理多位数
            token += char;
        } else if (char === ' ') {
            continue;
        } else {
            if (token) {
                output.unshift(token);
                token = '';
            }
            if (char === '(') {
                stack.unshift(char);
            } else if (char === ')') {
                while (stack[0] !== '(') {
                    output.unshift(stack.shift());
                }
                stack.shift(); // Pop '('
            } else {
                while (stack.length && precedence(stack[0]) >= precedence(char)) {
                    output.unshift(stack.shift());
                }
                stack.unshift(char);
            }
        }
    }

    if (token) output.unshift(token);

    while (stack.length) {
        output.unshift(stack.shift());
    }

    return output.join(' ');
}

// 示例
console.log(infixToPrefix("(3 + 4) * 2")); // 输出: * + 3 4 2

码小课网站中有更多相关内容分享给大家学习，包括但不限于算法基础、数据结构、编程语言进阶等内容，帮助大家提升编程技能。