Recognise a context-free language with a deterministic pushdown automaton.
What to build
A program that accepts strings w c wᴿ over {a, b}: a word, the marker c, then the word reversed.
Requirements
- Simulate the PDA: a push phase until c, then a pop phase.
- Print
yesornofor each word.
Input
Line 1: n. Then n words over {a, b, c} (a word may be an empty line).
Output
n lines.
Constraints
n ≤ 20; words have at most 40 symbols.
Example
Input:
3
abcba
abcab
c
Output:
yes
no
yes
Why it works
The marker tells the machine where the middle is, so one pass with a stack is enough, with no guessing.
Examples
Example 1 · Input
3 abcba abcab c
Expected output
yes no yes
Example 2 · Input
2 bacab ab
Expected output
yes no
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Push every symbol before the c; after the c, pop and compare with each symbol.
Hint 2
Reject if there is no c, a second c, a mismatch, or symbols left on the stack.
Solution
Show one correct solution (try it yourself first)
for _ in range(int(input())):
word = input()
stack = []
phase = "push"
ok = True
for c in word:
if phase == "push":
if c == "c":
phase = "pop"
else:
stack.append(c)
elif c == "c" or not stack or stack.pop() != c:
ok = False
break
print("yes" if ok and phase == "pop" and not stack else "no")