79 lines
2.4 KiB
Python
79 lines
2.4 KiB
Python
|
"""
|
|||
|
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)
|