Turn a regular expression into postfix form, ready to build an NFA with a stack.
What to build
A program that prints the postfix form of a regular expression, with . for concatenation.
Requirements
- Make concatenation explicit first.
- Print operands and operators in postfix order, with no spaces.
Input
One line: an expression of letters, digits, |, * and brackets.
Output
One line: the postfix form.
Constraints
At most 40 characters; the expression is well formed.
Example
Input:
a|b
Output:
ab|
Why it works
In postfix, each operator comes right after its operands, so a stack of NFA fragments can apply it immediately.
Examples
a|b
ab|
ab|c*
ab.c*|
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
First insert explicit `.` for concatenation, then run the shunting-yard algorithm.
Hint 2
Precedence: `*` (output at once, it follows its operand) > `.` > `|`; pop operators of equal or higher precedence before pushing.
Solution
Show one correct solution (try it yourself first)
regex = input()
tokens = []
for i, c in enumerate(regex):
if i > 0:
before = regex[i - 1]
if (before.isalnum() or before in ")*") and (c.isalnum() or c == "("):
tokens.append(".")
tokens.append(c)
precedence = {"|": 1, ".": 2}
out, stack = [], []
for t in tokens:
if t.isalnum() or t == "*":
out.append(t)
elif t == "(":
stack.append(t)
elif t == ")":
while stack[-1] != "(":
out.append(stack.pop())
stack.pop()
else:
while stack and stack[-1] != "(" and precedence[stack[-1]] >= precedence[t]:
out.append(stack.pop())
stack.append(t)
while stack:
out.append(stack.pop())
print("".join(out))
Lesson: From regular expression to NFA: Thompson's construction →