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)
|