pygorithm/stack/infix_conversion.py

79 lines
2.4 KiB
Python
Raw Permalink Normal View History

2023-11-29 19:31:30 +08:00
"""
1. 经观察可发现操作数的相对位置是不变的变化的只是操作符
2. 中转前
1 如果是一个操作数则看一眼操作符栈中的栈顶是否是 */
1.1. 如果是 */则先拿到这个操作数再从操作数栈弹出一个数
再弹出操作符拼接后放入操作数栈顶
1.2如果是 +-则将此操作数入操作数栈
2. 如果是一个 ( + - * /直接入操作符栈顶
3. 如果是 )则执行出栈直到遇到 (出栈的步骤跟 1.1
3. 中转后
1.
"""
from .stack import Stack
def infix_to_prefix(infix: str):
op_stack = Stack[str]()
num_stack = Stack[str]()
for item in infix:
if item in ['(', '*', '+', '-', '/']:
op_stack.push(item)
elif '0' <= item <= 'z':
if op_stack.peek() in ['*', '/']:
temp = num_stack.pop()
op = op_stack.pop()
num_stack.push(op + temp + item)
else:
num_stack.push(item)
elif item == ')':
op = op_stack.pop()
while op != '(':
temp1 = num_stack.pop()
temp2 = num_stack.pop()
num_stack.push(op + temp2 + temp1)
op = op_stack.pop()
if not op_stack.is_empty():
i1 = num_stack.pop()
i2 = num_stack.pop()
op = op_stack.pop()
return op + i2 + i1
else:
return num_stack.pop()
def infix_to_postfix(infix: str):
op_stack = Stack[str]()
num_stack = Stack[str]()
for item in infix:
if item in ['(', '*', '+', '-', '/']:
op_stack.push(item)
elif '0' <= item <= 'z':
if op_stack.peek() in ['*', '/']:
temp = num_stack.pop()
op = op_stack.pop()
num_stack.push(temp + item + op)
else:
num_stack.push(item)
elif item == ')':
op = op_stack.pop()
while op != '(':
temp1 = num_stack.pop()
temp2 = num_stack.pop()
num_stack.push(temp2 + temp1 + op)
op = op_stack.pop()
if not op_stack.is_empty():
i1 = num_stack.pop()
i2 = num_stack.pop()
op = op_stack.pop()
return i2 + i1 + op
else:
return num_stack.pop()
res = infix_to_prefix('a+b*c')
print(res)