Expression Tokenizer
Problem
The line is an arithmetic expression with whole numbers, the operators + - * / and the brackets ( ). Spaces may appear anywhere. Split it into tokens: a token is a whole number or a single operator or bracket. Print every token on its own line, from left to right.
Constraints
- 1 <= length <= 10^4
- only digits, + - * / ( ) and spaces
Examples
Input
12+(3 * 4)
Output
12 + ( 3 * 4 )
Solutions
A scanner reads one character at a time. A digit means keep reading digits. Anything else is a single-character token. This is the first stage of every calculator and compiler.
/*
* Problem : Split into tokens.
* Input : One expression.
* Output : One token per line.
* Approach: Character scanner.
* Time : O(n)
* Space : O(n)
* Java : 8 or newer.
*/
import java.util.Scanner;
public class Main {
// This method solves the task. It receives the input and returns the answer.
static String[] solve(String s) {
// Step 1: Scan the characters from left to right. A digit starts a number: read all the digits that follow.
java.util.List<String> tokens = new java.util.ArrayList<String>();
int i = 0;
while (i < s.length()) {
char c = s.charAt(i);
if (Character.isDigit(c)) {
int start = i;
while (i < s.length() && Character.isDigit(s.charAt(i))) {
i++;
}
tokens.add(s.substring(start, i));
} else {
// Step 2: Spaces are skipped. Every other character is a one-character token.
if (c != ' ') {
tokens.add(String.valueOf(c));
}
i++;
}
}
return tokens.toArray(new String[0]);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.hasNextLine() ? scanner.nextLine() : "";
System.out.println(String.join("\n", solve(s)));
}
}
Hints (2)
- Why read all the digits after the first one?
- What do we do with a space?