17 "/" -> 2) |
17 "/" -> 2) |
18 |
18 |
19 // helper function for splitting strings into tokens |
19 // helper function for splitting strings into tokens |
20 def split(s: String) : Toks = s.split(" ").toList |
20 def split(s: String) : Toks = s.split(" ").toList |
21 |
21 |
|
22 // ADD YOUR CODE BELOW |
|
23 //====================== |
22 |
24 |
23 // (1) Implement below the shunting yard algorithm. The most |
|
24 // convenient way to this in Scala is to implement a recursive |
|
25 // function and to heavily use pattern matching. The function syard |
|
26 // takes some input tokens as first argument. The second and third |
|
27 // arguments represent the stack and the output of the shunting yard |
|
28 // algorithm. |
|
29 // |
|
30 // In the marking, you can assume the function is called only with |
|
31 // an empty stack and an empty output list. You can also assume the |
|
32 // input os only properly formatted (infix) arithmetic expressions |
|
33 // (all parentheses will be well-nested, the input only contains |
|
34 // operators and numbers). |
|
35 |
25 |
36 // You can implement any additional helper function you need. I found |
26 // (1) |
37 // it helpful to implement two auxiliary functions for the pattern matching: |
|
38 // |
|
39 |
|
40 def is_op(op: String) : Boolean = ??? |
27 def is_op(op: String) : Boolean = ??? |
41 def prec(op1: String, op2: String) : Boolean = ??? |
28 def prec(op1: String, op2: String) : Boolean = ??? |
42 |
|
43 |
29 |
44 def syard(toks: Toks, st: Toks = Nil, out: Toks = Nil) : Toks = ??? |
30 def syard(toks: Toks, st: Toks = Nil, out: Toks = Nil) : Toks = ??? |
45 |
31 |
46 |
32 |
47 // test cases |
33 // test cases |
56 //syard(split("( ( 3 + 4 ) + 5 )")) // 3 4 + 5 + |
42 //syard(split("( ( 3 + 4 ) + 5 )")) // 3 4 + 5 + |
57 //syard(split("( 3 + ( 4 + 5 ) )")) // 3 4 5 + + |
43 //syard(split("( 3 + ( 4 + 5 ) )")) // 3 4 5 + + |
58 //syard(split("( ( ( 3 ) ) + ( ( 4 + ( 5 ) ) ) )")) // 3 4 5 + + |
44 //syard(split("( ( ( 3 ) ) + ( ( 4 + ( 5 ) ) ) )")) // 3 4 5 + + |
59 |
45 |
60 |
46 |
61 // (2) Implement a compute function that evaluates an input list |
47 // (2) |
62 // in postfix notation. This function takes a list of tokens |
|
63 // and a stack as argumenta. The function should produce the |
|
64 // result as an integer using the stack. You can assume |
|
65 // this function will be only called with proper postfix |
|
66 // expressions. |
|
67 |
|
68 def compute(toks: Toks, st: List[Int] = Nil) : Int = ??? |
48 def compute(toks: Toks, st: List[Int] = Nil) : Int = ??? |
69 |
49 |
70 |
50 |
71 // test cases |
51 // test cases |
72 // compute(syard(split("3 + 4 * ( 2 - 1 )"))) // 7 |
52 // compute(syard(split("3 + 4 * ( 2 - 1 )"))) // 7 |