equal
deleted
inserted
replaced
1 // Shunting Yard Algorithm |
1 // Shunting Yard Algorithm |
2 // by Edsger Dijkstra |
2 // by Edsger Dijkstra |
3 // ======================== |
3 // ======================== |
4 |
4 |
|
5 object CW9a { |
5 |
6 |
6 // type of tokens |
7 // type of tokens |
7 type Toks = List[String] |
8 type Toks = List[String] |
8 |
9 |
9 // the operations in the basic version of the algorithm |
10 // the operations in the basic version of the algorithm |
17 |
18 |
18 // helper function for splitting strings into tokens |
19 // helper function for splitting strings into tokens |
19 def split(s: String) : Toks = s.split(" ").toList |
20 def split(s: String) : Toks = s.split(" ").toList |
20 |
21 |
21 |
22 |
22 // (6) Implement below the shunting yard algorithm. The most |
23 // (1) Implement below the shunting yard algorithm. The most |
23 // convenient way to this in Scala is to implement a recursive |
24 // convenient way to this in Scala is to implement a recursive |
24 // function and to heavily use pattern matching. The function syard |
25 // function and to heavily use pattern matching. The function syard |
25 // takes some input tokens as first argument. The second and third |
26 // takes some input tokens as first argument. The second and third |
26 // arguments represent the stack and the output of the shunting yard |
27 // arguments represent the stack and the output of the shunting yard |
27 // algorithm. |
28 // algorithm. |
54 //syard(split("( ( 3 + 4 ) + 5 )")) // 3 4 + 5 + |
55 //syard(split("( ( 3 + 4 ) + 5 )")) // 3 4 + 5 + |
55 //syard(split("( 3 + ( 4 + 5 ) )")) // 3 4 5 + + |
56 //syard(split("( 3 + ( 4 + 5 ) )")) // 3 4 5 + + |
56 //syard(split("( ( ( 3 ) ) + ( ( 4 + ( 5 ) ) ) )")) // 3 4 5 + + |
57 //syard(split("( ( ( 3 ) ) + ( ( 4 + ( 5 ) ) ) )")) // 3 4 5 + + |
57 |
58 |
58 |
59 |
59 // (7) Implement a compute function that evaluates an input list |
60 // (2) Implement a compute function that evaluates an input list |
60 // in postfix notation. This function takes a list of tokens |
61 // in postfix notation. This function takes a list of tokens |
61 // and a stack as argumenta. The function should produce the |
62 // and a stack as argumenta. The function should produce the |
62 // result as an integer using the stack. You can assume |
63 // result as an integer using the stack. You can assume |
63 // this function will be only called with proper postfix |
64 // this function will be only called with proper postfix |
64 // expressions. |
65 // expressions. |
72 // compute(syard(split("( 5 + 7 ) * 2"))) // 24 |
73 // compute(syard(split("( 5 + 7 ) * 2"))) // 24 |
73 // compute(syard(split("5 + 7 / 2"))) // 8 |
74 // compute(syard(split("5 + 7 / 2"))) // 8 |
74 // compute(syard(split("5 * 7 / 2"))) // 17 |
75 // compute(syard(split("5 * 7 / 2"))) // 17 |
75 // compute(syard(split("9 + 24 / ( 7 - 3 )"))) // 15 |
76 // compute(syard(split("9 + 24 / ( 7 - 3 )"))) // 15 |
76 |
77 |
|
78 } |
77 |
79 |
78 |
80 |
79 |
|