Theory: A regular expression in postfix

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

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