Theory: Make concatenation explicit

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

Example 1 · Input
ab|c*
Expected output
a.b|c*
Example 2 · Input
(a|b)*abb
Expected output
(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 →