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