算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法,即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。 输入格式: 输入在一行中给出不含空格的中缀表达式,可包含+、-、*、/以及左右括号(),表达式不超过20个字符。 输出格式: 在一行中输出转换后的后缀表达式,要求不同对象(运算数、运算符号)之间以空格分隔,但结尾不得有多余空格。编写代码
时间: 2024-02-18 07:59:01 浏览: 86
好的,下面是 Python 代码实现。该程序使用了栈来完成中缀表达式到后缀表达式的转换:
```
OPERATORS = {'+': 1, '-': 1, '*': 2, '/': 2, '(': 0, ')': 0}
def infix_to_postfix(infix):
stack = []
postfix = []
for token in infix:
if token.isdigit():
postfix.append(token)
elif token in OPERATORS:
while stack and OPERATORS[token] <= OPERATORS[stack[-1]]:
postfix.append(stack.pop())
stack.append(token)
elif token == '(':
stack.append(token)
elif token == ')':
while stack and stack[-1] != '(':
postfix.append(stack.pop())
stack.pop()
while stack:
postfix.append(stack.pop())
return ' '.join(postfix)
if __name__ == '__main__':
infix = input().strip()
postfix = infix_to_postfix(infix)
print(postfix)
```
程序中,我们定义了一个字典 `OPERATORS`,用于存储运算符的优先级。然后我们遍历中缀表达式中的每个元素,如果是数字,则直接输出到后缀表达式中;如果是运算符,则根据其优先级与栈顶运算符的优先级进行比较,如果栈顶运算符的优先级更高,则弹出栈顶运算符并输出,直到栈顶运算符的优先级小于等于当前运算符的优先级,然后将当前运算符入栈。如果是左括号,则直接入栈;如果是右括号,则弹出栈顶元素并输出,直到遇到左括号为止。最后,我们将栈中剩余的元素全部弹出并输出,即得到了后缀表达式。
阅读全文