Parser

Parse Lisp Expression

1
2
3
4
5
6
7
8
9
10
11
12
(let  v1 e1 v2 e2 ... vn en expr)
(add e1 e2)
(mult e1 e2)

(add 1 2) -> 3
(mult 3 (add 2 3)) -> 15
(let x 2 (mult x 5)) -> 10
(let x 2 (mult x (let x 3 y 4 (add x y)))) -> 14
(let x 3 x 2 x) -> 2
(let x 1 y 2 x (add x y) (add x y)) -> 5
(let x 2 (add (let x 3 (let x 4 x)) x)) -> 6
(let a1 3 b2 (add a1 1) b2) -> 4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
int evaluate(string expression) {
unordered_map<string,int> myMap;
return help(expression,myMap);
}

int help(string expression,unordered_map<string,int> myMap) {
if ((expression[0] == '-') || (expression[0] >= '0' && expression[0] <= '9'))
return stoi(expression);
else if (expression[0] != '(')
return myMap[expression];
//to get rid of the first '(' and the last ')'
string s = expression.substr(1,expression.size()-2);
int start = 0;
string word = parse(s,start);
if (word == "let") {
while (true) {
string variable = parse(s,start);
//if there is no more expression, simply evaluate the variable
if (start > s.size())
return help(variable,myMap);
string temp = parse(s,start);
myMap[variable] = help(temp,myMap);
}
}
else if (word == "add")
return help(parse(s,start),myMap) + help(parse(s,start),myMap);
else if (word == "mult")
return help(parse(s,start),myMap) * help(parse(s,start),myMap);
}

//function to seperate each expression
string parse(string &s,int &start) {
int end = start+1, temp = start, count = 1;
if (s[start] == '(') {
while (count != 0) {
if (s[end] == '(')
count++;
else if (s[end] == ')')
count--;
end++;
}
}
else {
while (end < s.size() && s[end] != ' ')
end++;
}
start = end+1;
return s.substr(temp,end-temp);
}