Benjamin Halsted // [bgh] todo, add something clever here.

Erlang Programming Exercise: 3-8-1

When I made it to exercise 3-8 my jaw hit the floor. How did we go from using the lists module to writing a parser for arithmetical expressions? This first part of this exercise took me weeks. I worked my way through it after many revisions and scrapping the whole thing two times. Since the instructions are long, I've summed it up:

Write a parser turning expressions like ((2+3)-4) into Erlang representation {minus, {plus, {num, 2}, {num,3}}, {num, 4}}

My first version didn't have a stack and could only parse expressions where it didn't have to remember anything. ((2+3)+4) it could handle, but not (4+(3+2)) because it would have to remember that it was in the middle of parsing the 4+X expression when it had to parse the (3+2) part.

My second version had a stack and could handle parsing expressions like (4+(3+2)) and ((2+3)+4), but it could not handle parsing ((2+3)+(4+(5+6))). It would parse the (2+3) just fine and start into the second half, and could parse it, but I wasn't keeping track of what was left to be parsed, so it became confused at that point and would crash.

Here is my third revision. Note that it doesn't implement the unary minus (~) from the instructions. So far it only supports well formed expressions that use ()+- and single digit numbers.

-module(threeeightyone).
-export([parser/1]).

getNextExpressionUntil(Stack, [Until|String], Until) ->
	{Stack, String};
getNextExpressionUntil(Stack, String, Until) ->
	{Expression, ModifiedStack, StringLeft} = getNextExpression(Stack, String),
	getNextExpressionUntil([Expression|ModifiedStack], StringLeft, Until).

getNextOperator(Op, [PreviousExpression|RemainingStack], String) ->
	{NextExpression, ModifiedStack, RemainingString} = getNextExpression(RemainingStack, String),
	{{Op, PreviousExpression, NextExpression}, ModifiedStack, RemainingString}.

getNextExpression(Stack, [$(|String]) ->
	{Expression, [], RemainingString1} = getNextExpression([], String),
	{[NextExpression|_T], RemainingString2} = getNextExpressionUntil([Expression], RemainingString1, $)),
	{NextExpression, Stack, RemainingString2};

getNextExpression(Stack, [$+|String]) ->
	getNextOperator(plus, Stack, String);
getNextExpression(Stack, [$-|String]) ->
	getNextOperator(minus, Stack, String);

% 0=48 9=57
getNextExpression(Stack, [H|String]) when H >= 48 , H =< 57->
	{{num, H-48}, Stack, String};

getNextExpression(Stack, [H|String]) ->
	{H, Stack, String}.

parseString(Stack, []=_String) ->
	lists:reverse(Stack);
parseString(Stack, String) ->
	{Expression, ModifiedStack, StringLeft} = getNextExpression(Stack, String),
	parseString([Expression|ModifiedStack], StringLeft).

parseString(String) ->
	parseString([], String).

parser(String) ->
	parseString(String).

Something new for me was the use of the dollar sign. It lets you specify a literal character. If you want to look for the letter A, you would write $A. If you wanted a dollar sign, you would write $$.

Cheers,
-Halzy