PDA Stack Python 文件问题

Question

这是我当前的代码：

def simulate(self, input_string):
        stack = []
        current_state = self.start_state
        input_index = 0

        while input_index < len(input_string):
            current_symbol = input_string[input_index]

            # Find applicable transition
            transition = None
            for t in self.transitions:
                if (
                    t[0] == current_state
                    and t[2] == current_symbol
                    and (t[3] == "any" or (t[3] == "empty" and not stack) or (t[3] in self.alphabet and stack[-1] == t[3]))
                ):
                    transition = t
                    break

            # If no applicable transition is found, reject the string
            if transition is None:
                print("Rejected")
                return

            # Update current state
            current_state = transition[1]

            # Update stack based on stack operation
            if transition[4] == "pop":
                popped = stack.pop()
            elif transition[4].startswith("push"):
                stack.extend(list(transition[4].split()[1]))
                popped = ""
            else:
                popped = ""

            # Print current configuration
            if current_symbol != "*":
                print(f"{current_symbol} {current_state} {popped} {transition[4]} {''.join(stack[::-1])}")
            else:
                print(f"* {current_state} {popped} {transition[4]} {''.join(stack[::-1])}")

            # Move to the next symbol in the input string
            input_index += 1

        # Check if the final state is accepting
        if current_state in self.accepting_states:
            print(f"{current_state} [] accept")
        else:
            print("Rejected")

这是所需的输出：

Enter input string: 10110*01101#
1 q0 [] push 1
0 q0 [1] push 0
1 q0 [10] push 1
1 q0 [101] push 1
0 q0 [1011] push 0
* q0 [10110] none
0 q1 [10110] pop
1 q1 [1011] pop
1 q1 [101] pop
0 q1 [10] pop
1 q1 [1] pop
# q1 [] none
q2 [] accept

这是我的输出：

Enter input string: 10110*01101#
1 q0  push 1 1
0 q0  push 0 01
1 q0  push 1 101
1 q0  push 1 1101
0 q0  push 0 01101
* q1  none 01101
0 q1 0 pop 1101
1 q1 1 pop 101
1 q1 1 pop 01
0 q1 0 pop 1
1 q1 1 pop
# q2  none
q2 [] accept

正如您所看到的，推送的顺序似乎是错误的。我该如何解决这个问题？

我尝试通过反转并使用 (-1) 来更改 stack.extend 方法，但没有任何效果。任何建议都会有很大帮助。此外，关于如何将内容包含在 [] 中的建议也会有很大帮助。非常感谢！ 第一次推送似乎存在问题，并且第一行堆栈中已经有 1，而此时所需的输出堆栈中没有任何内容。我发现 * 行和 # 行的状态错误 - 我该如何修复这些问题？

Answer 1

问题似乎出在“推”转换期间更新堆栈的方式。问题是您正在按照字符在转换字符串中出现的顺序扩展堆栈，但您希望它们以相反的顺序推送。

这是解决此问题的代码的修改部分：

# Update stack based on stack operation
if transition[4] == "pop":
    popped = stack.pop()
elif transition[4].startswith("push"):
    # Reverse the characters before pushing them onto the stack
    push_chars = list(transition[4].split()[1])[::-1]
    stack.extend(push_chars)
    popped = ""
else:
    popped = ""

此修改确保字符按照预期按相反顺序压入堆栈。通过此更改，输出应该更接近所需的输出。

关于在输出中包含

[]

中的内容，可以修改打印语句如下：

print(f"{current_symbol} {current_state} [{', '.join(stack[::-1])}] {transition[4]} {''.join(stack[::-1])}")

此修改打印

[]

内堆栈的内容。确保根据您的具体格式偏好进行调整。

通过这些更改，您的输出应该与所需的输出更加一致。如果仍然存在问题，您可能需要仔细检查更新当前状态和其他条件的逻辑，以确保它们符合所需的行为。