Prepare a regular expression for a stack-based parser.
What to build
A program that rewrites a regular expression with . written wherever two pieces are joined.
Requirements
- Insert
.exactly where concatenation happens, and change nothing else.
Input
One line: an expression of letters, digits, |, * and brackets.
Output
The expression with explicit concatenation.
Constraints
At most 40 characters; the expression is well formed.
Example
Input:
ab|c*
Output:
a.b|c*
Why it works
Concatenation has no symbol of its own; writing it as . lets the shunting-yard algorithm treat it like any other operator.
Examples
ab|c*
a.b|c*
(a|b)*abb
(a|b)*.a.b.b
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Insert `.` between two characters x and y when x is a symbol, `)` or `*`, and y is a symbol or `(`.
Hint 2
Symbols are letters or digits; `|`, `*`, `(` and `)` are operators.
Solution
Show one correct solution (try it yourself first)
regex = input()
out = []
for i, c in enumerate(regex):
if i > 0:
before = regex[i - 1]
if (before.isalnum() or before in ")*") and (c.isalnum() or c == "("):
out.append(".")
out.append(c)
print("".join(out))
Lesson: From regular expression to NFA: Thompson's construction →