Under construction

Still being built. Things may change

Tokenizer

Interview

Time limit1sMemory limit1024 MB

Summary
Split a shell command line at the delimiters <, >, &&, ||, (, ), and spaces, then print the non-space tokens separated by single spaces.
Level

Easy3 of 10

Topics
String, Implementation
Solved
No attempts yet

Problem

Joowon is building a shell that gives users a text interface for interacting with the system. When the shell receives a command line, it calls the tokenizer, lexer, parser, expander, and executor in that order to interpret the command and run a valid program. Joowon first needs a tokenizer that splits a command line at the delimiters below. Joowon has always split strings on spaces only and finds it hard to split a command at several delimiters. Help Joowon build this tokenizer.

DelimiterCommandOutput example
<cat <infilecat < infile
>program >outfileprogram > outfile
&&program&&echo successprogram && echo success
||grep sol < for||echo failgrep sol < for || echo fail
((exit 0)( exit 0 )
)(cd $OLDPWD ) && pwd( cd $OLDPWD ) && pwd
" " (space)echo 1 2 3 4echo 1 2 3 4

The tokenizer works as follows.

  1. Read the string from the front.
  2. When a delimiter is found, cut the string on both sides of the delimiter. Then continue reading from the position right after the delimiter. Each cut piece is called a token.
  3. When the end of the string is reached, print the tokens from front to back, separated by single spaces. Tokens that are a single space are not printed.

Let S be grep skku <infile> outfile. When S is split into tokens by the character :, the result is:

grep: :skku: : : :<:infile:>: :outfile

Remove the tokens that consist only of a single space, and print the rest in order, separated by single spaces. For this S, the output is grep skku < infile > outfile.

Input

The first line contains the shell command S. The command consists of delimiters, uppercase and lowercase English letters, digits, and $, ?, +, _. No run of & or | characters occurs an odd number of times in a row.

(∣S∣≤1 000 000)(|S|\le1\,000\,000)

Output

Split the command S at the delimiters, then print the tokens separated by single spaces. Do not print tokens that consist only of a single space.

Examples3

  1. Example 1

    Input
    grep skku   <infile> outfile
    
    Expected output
    grep skku < infile > outfile
    
  2. Example 2

    Input
    (exit $?  )||expr $? + $?
    
    Expected output
    ( exit $? ) || expr $? + $?
    
  3. Example 3

    Input
    grep Wall <Makefile|| echo NotSetCflagsWall>outfile
    
    Expected output
    grep Wall < Makefile || echo NotSetCflagsWall > outfile