1 // Shunting Yard Algorithm |
1 // Shunting Yard Algorithm |
2 // by Edsger Dijkstra |
2 // by Edsger Dijkstra |
3 // ======================== |
3 // ======================== |
4 |
4 |
5 |
5 |
6 |
6 // type of tokens |
7 type Toks = List[String] |
7 type Toks = List[String] |
8 |
8 |
9 // the operations in the simple version |
9 // the operations in the basic version of the algorithm |
10 val ops = List("+", "-", "*", "/") |
10 val ops = List("+", "-", "*", "/") |
11 |
11 |
12 // the precedences of the operators |
12 // the precedences of the operators |
13 val precs = Map("+" -> 1, |
13 val precs = Map("+" -> 1, |
14 "-" -> 1, |
14 "-" -> 1, |
19 def split(s: String) : Toks = s.split(" ").toList |
19 def split(s: String) : Toks = s.split(" ").toList |
20 |
20 |
21 |
21 |
22 // (6) Implement below the shunting yard algorithm. The most |
22 // (6) Implement below the shunting yard algorithm. The most |
23 // convenient way to this in Scala is to implement a recursive |
23 // convenient way to this in Scala is to implement a recursive |
24 // function using pattern matching. The function takes some input |
24 // function and to heavily use pattern matching. The function syard |
25 // tokens as first argument. The second and third arguments represent |
25 // takes some input tokens as first argument. The second and third |
26 // the stack and the output or the shunting yard algorithm. |
26 // arguments represent the stack and the output of the shunting yard |
|
27 // algorithm. |
27 // |
28 // |
28 // In the marking, you can assume the function is called only with |
29 // In the marking, you can assume the function is called only with |
29 // an empty stack and empty output list. You can also assume the |
30 // an empty stack and an empty output list. You can also assume the |
30 // input are only properly formated (infix) arithmetic expressions |
31 // input os only properly formatted (infix) arithmetic expressions |
31 // (for example all parentheses are well-nested, the input only contains |
32 // (all parentheses will be well-nested, the input only contains |
32 // operators and numbers). |
33 // operators and numbers). |
33 |
34 |
34 // You can implement any helper function you need. I found it helpful |
35 // You can implement any additional helper function you need. I found |
35 // to implement auxiliary functions: |
36 // it helpful to implement two auxiliary functions for the pattern matching: |
36 |
37 // |
37 def is_op(op: String) : Boolean = ops.contains(op) |
38 // def is_op(op: String) : Boolean = ... |
38 |
39 // def prec(op1: String, op2: String) : Boolean = ... |
39 def prec(op1: String, op2: String) : Boolean = precs(op1) <= precs(op2) |
|
40 |
40 |
41 |
41 |
42 def syard(toks: Toks, st: Toks = Nil, out: Toks = Nil) : Toks = (toks, st, out) match { |
42 // def syard(toks: Toks, st: Toks = Nil, out: Toks = Nil) : Toks = ... |
43 case (Nil, _, _) => out.reverse ::: st |
|
44 case (num::in, st, out) if (num.forall(_.isDigit)) => |
|
45 syard(in, st, num :: out) |
|
46 case (op1::in, op2::st, out) if (is_op(op1) && is_op(op2) && prec(op1, op2)) => |
|
47 syard(op1::in, st, op2 :: out) |
|
48 case (op1::in, st, out) if (is_op(op1)) => syard(in, op1::st, out) |
|
49 case ("("::in, st, out) => syard(in, "("::st, out) |
|
50 case (")"::in, op2::st, out) => |
|
51 if (op2 == "(") syard(in, st, out) else syard(")"::in, st, op2 :: out) |
|
52 case (in, st, out) => { |
|
53 println(s"in: ${in} st: ${st} out: ${out.reverse}") |
|
54 Nil |
|
55 } |
|
56 } |
|
57 |
43 |
58 |
44 |
59 // test cases |
45 // test cases |
60 //syard(split("3 + 4 * ( 2 - 1 )")) // 3 4 2 1 - * + |
46 //syard(split("3 + 4 * ( 2 - 1 )")) // 3 4 2 1 - * + |
61 //syard(split("10 + 12 * 33")) // 10 12 33 * + |
47 //syard(split("10 + 12 * 33")) // 10 12 33 * + |
69 //syard(split("( 3 + ( 4 + 5 ) )")) // 3 4 5 + + |
55 //syard(split("( 3 + ( 4 + 5 ) )")) // 3 4 5 + + |
70 //syard(split("( ( ( 3 ) ) + ( ( 4 + ( 5 ) ) ) )")) // 3 4 5 + + |
56 //syard(split("( ( ( 3 ) ) + ( ( 4 + ( 5 ) ) ) )")) // 3 4 5 + + |
71 |
57 |
72 |
58 |
73 // (7) Implement a compute function that evaluates an input list |
59 // (7) Implement a compute function that evaluates an input list |
74 // in postfix notation. This function takes an input list of tokens |
60 // in postfix notation. This function takes a list of tokens |
75 // and a stack as argument. The function should produce the |
61 // and a stack as argumenta. The function should produce the |
76 // result in form of an integer using the stack. You can assume |
62 // result as an integer using the stack. You can assume |
77 // this function will be only called with proper postfix expressions. |
63 // this function will be only called with proper postfix |
|
64 // expressions. |
78 |
65 |
79 def op_comp(s: String, n1: Int, n2: Int) = s match { |
66 // def compute(toks: Toks, st: List[Int] = Nil) : Int = ... |
80 case "+" => n2 + n1 |
|
81 case "-" => n2 - n1 |
|
82 case "*" => n2 * n1 |
|
83 case "/" => n2 / n1 |
|
84 } |
|
85 |
67 |
86 def compute(toks: Toks, st: List[Int] = Nil) : Int = (toks, st) match { |
|
87 case (Nil, st) => st.head |
|
88 case (op::in, n1::n2::st) if (is_op(op)) => compute(in, op_comp(op, n1, n2)::st) |
|
89 case (num::in, st) => compute(in, num.toInt::st) |
|
90 } |
|
91 |
68 |
92 // test cases |
69 // test cases |
93 // compute(syard(split("3 + 4 * ( 2 - 1 )"))) // 7 |
70 // compute(syard(split("3 + 4 * ( 2 - 1 )"))) // 7 |
94 // compute(syard(split("10 + 12 * 33"))) // 406 |
71 // compute(syard(split("10 + 12 * 33"))) // 406 |
95 // compute(syard(split("( 5 + 7 ) * 2"))) // 24 |
72 // compute(syard(split("( 5 + 7 ) * 2"))) // 24 |