当前位置： 面试刷题>> 将表达式转换为波兰表达式 (经典算法题500道)
### 题目描述补充
题目：**将表达式转换为波兰表达式（也称为前缀表达式）**
波兰表达式是一种数学表达式的表示方法，其中运算符位于其操作数之前。例如，算术表达式 `(3 + 4) * 2` 转换为波兰表达式为 `* + 3 4 2`。请编写一个函数，该函数接收一个包含数字和运算符（`+`, `-`, `*`, `/`）的中缀表达式字符串作为输入，并返回其对应的波兰表达式字符串。
注意：
1. 输入的中缀表达式是有效的，即括号正确匹配，运算符仅包含 `+`, `-`, `*`, `/`，操作数仅包含非负整数。
2. 假设除法总是整数除法。
### 示例代码
#### PHP 示例
```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 示例
```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 示例
```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
```
**码小课网站中有更多相关内容分享给大家学习**，包括但不限于算法基础、数据结构、编程语言进阶等内容，帮助大家提升编程技能。