Write a parser that accepts command line arguments.
For each command line argument, print out true or false,
depending on whether or not that value parses.
For a value to parse, it must consist entirely of these
characters: '(', ')', '[', ']‘. Any other character renders
the parse invalid and so prints “false”.
The value must also be “balanced”. That is, for each opening
parenthesis or bracket, it is matched by a closing parenthesis
or bracket accordingly. The different bracket types must not
intersperse.
Here are some examples of successfully parsing values that
result in printing “true”:
""
"()"
"[]"
"([])"
"[()]"
"[]()"
"[][[([])]]"
Here are some examples of values that fail the parsing and
result in printing “false”:
"("
")"
"["
"]"
"]["
")("
"( )"
"([)"
"[)]"
"([)]"
"({})"
"[())]"
Using Haskell (without Parsec):
import Prelude hiding (foldr, any)
import Control.Monad
import Data.Foldable
import System
tokens = [('(', ')'), ('[', ']')]
parse x = any null (foldr (\c f -> (\s -> (const (c:s)) `fmap`
flip lookup ((uncurry (flip (,))) `fmap` tokens) c `mplus`
(flip lookup tokens c >>= (\v ->
do h:t <- return s
guard (v == h)
return t))) =<< f) (return []) x)
main = getArgs >>= print . (parse `fmap`)Using Scala (without scala.util.parsing):
object Parser {
val tokens = List(('(', ')'), ('[', ']'))
def parse(s: String) =
s.foldRight[Option[String]](Some(""))((a, b) => b flatMap
(ss => {
val s = ss.toList
(lookup(tokens map { case (x, y) => (y, x) }, a)
map (t => (a::s)) orElse
(lookup(tokens, a) flatMap (v => s match {
case Nil => None
case h :: t => if(v == h) Some(t) else None
}))) map (_.mkString)
})) exists (_.isEmpty)
def main(args: Array[String]) {
args foreach (parse _ andThen println)
}
// The Scala API needs hand-holding
def lookup[A, B](x: List[(A, B)], a: A) =
x.find { case (aa, _) => a == aa } map (_._2)
}Using Java 1.5 and Functional Java:
import fj.F;
import fj.F2;
import fj.Function;
import static fj.P.p;
import fj.P1;
import fj.P2;
import fj.data.List;
import static fj.data.List.asString;
import static fj.data.List.fromString;
import static fj.data.List.list;
import static fj.data.List.lookup;
import fj.data.Option;
import static fj.data.Option.some;
import static fj.function.Strings.isEmpty;
import static fj.pre.Equal.charEqual;
import static fj.pre.Show.booleanShow;
final class Parser {
@SuppressWarnings("unchecked")
static final List<P2<Character, Character>> tokens =
list(p('(', ')'), p('[', ']'));
static boolean parse(final String s) {
return fromString(s).foldRight(
new F2<Character, Option<String>, Option<String>>() {
public Option<String> f(final Character c, final Option<String> b) {
return b.bind(new F<String, Option<String>>() {
public Option<String> f(String s) {
final List<Character> ss = fromString(s);
return lookup(charEqual,
tokens.map(P2.<Character, Character>swap_()), c)
.map(Function.<Character,
List<Character>>constant(ss.cons(c)))
.orElse(lookup(charEqual, tokens, c)
.bind(new F<Character, Option<List<Character>>>() {
public Option<List<Character>> f(final Character v) {
return ss.isEmpty() || v != ss.head() ?
Option.<List<Character>>none() :
some(ss.tail());
}
})).map(asString());
}
});
}
}, some("")).exists(isEmpty);
}
public static void main(final String[] args) {
for(final String s : args) {
booleanShow.println(parse(s));
}
}
}Using Java BGGA and Functional Java:
import fj.Function;
import static fj.P.p;
import fj.P1;
import fj.P2;
import fj.data.List;
import static fj.data.List.asString;
import static fj.data.List.fromString;
import static fj.data.List.list;
import static fj.data.List.lookup;
import fj.data.Option;
import static fj.data.Option.some;
import static fj.function.Strings.isEmpty;
import static fj.pre.Equal.charEqual;
import static fj.pre.Show.booleanShow;
final class ParserBGGA {
@SuppressWarnings("unchecked")
static final List<P2<Character, Character>> tokens =
list(p('(', ')'), p('[', ']'));
static boolean parse(final String s) {
return fromString(s).foldRight({ char c, Option<String> b =>
b.bind({ String ss =>
final List<Character> s = fromString(ss);
lookup(charEqual,
tokens.map(P2.<Character, Character>swap_()), c)
.map(Function.<Character, List<Character>>constant(s.cons(c)))
.orElse(lookup(charEqual, tokens, c)
.bind({ char v =>
s.isEmpty() || v != s.head() ?
Option.<List<Character>>none() :
some(s.tail())})).map(asString())})}
, some("")).exists(isEmpty);
}
public static void main(final String[] args) {
for(final String s : args) {
booleanShow.println(parse(s));
}
}
}A submission by a Java programmer who volunteered:
import java.util.ArrayList;
public class IsBalanced {
private Stack stack = new Stack();
public boolean isBalanced(String expression) {
boolean isBalanced = true;
for (int i = 0; i < expression.length(); i++) {
char nextChar = expression.charAt(i);
if (nextChar == '(') {
stack.push('(');
}
else if (nextChar == '[') {
stack.push('[');
} else {
if (!stack.isEmpty()) {
char stackChar = (Character) stack.peek();
if (nextChar == ')') {
if (stackChar == '(') {
stack.pop();
} else {
return false;
}
} else if (nextChar == ']') {
if (stackChar == '[') {
stack.pop();
} else {
return false;
}
}
} else {
return false;
}
}
}
if (!stack.isEmpty()) {
isBalanced = false;
}
return isBalanced;
}
public static void main(String[] args) {
System.out.println(args[0]);
System.out.println((new IsBalanced()).isBalanced(args[0]));
}
private class Stack {
private ArrayList stack = new ArrayList();
public void push(char c) {
stack.add(c);
}
public void pop() {
stack.remove(stack.size()-1);
}
public Object peek() {
return stack.get(stack.size()-1);
}
public boolean isEmpty() {
return stack.size() == 0;
}
}
}Forget the syntax for a moment and consider the compositional properties of each of these programs. For example, what if I were to add another pair of brackets such as '{' and '}'? Are there sub-programs that exist independently and can be extracted from the larger program? How does that affect my ability to reason (and therefore, read) the code?
What properties about the code make it easy to read?
