1 // Shunting Yard Algorithm |
1 // Shunting Yard Algorithm |
2 // Edsger Dijkstra |
2 // including Associativity for Operators |
|
3 // ===================================== |
|
4 |
|
5 // type of tokens |
|
6 type Toks = List[String] |
|
7 |
|
8 // helper function for splitting strings into tokens |
|
9 def split(s: String) : Toks = s.split(" ").toList |
|
10 |
|
11 // left- and right-associativity |
|
12 abstract class Assoc |
|
13 case object LA extends Assoc |
|
14 case object RA extends Assoc |
3 |
15 |
4 |
16 |
5 type Toks = List[String] |
17 // power is right-associative, |
6 |
18 // everything else is left-associative |
7 def split(s: String) = s.split(" ").toList |
|
8 |
|
9 |
|
10 abstract class Assoc |
|
11 case object RA extends Assoc |
|
12 case object LA extends Assoc |
|
13 |
|
14 def assoc(s: String) : Assoc = s match { |
19 def assoc(s: String) : Assoc = s match { |
15 case "^" => RA |
20 case "^" => RA |
16 case _ => LA |
21 case _ => LA |
17 } |
22 } |
18 |
23 |
19 |
24 |
|
25 // the precedences of the operators |
20 val precs = Map("+" -> 1, |
26 val precs = Map("+" -> 1, |
21 "-" -> 1, |
27 "-" -> 1, |
22 "*" -> 2, |
28 "*" -> 2, |
23 "/" -> 2, |
29 "/" -> 2, |
24 "^" -> 4) |
30 "^" -> 4) |
25 |
31 |
|
32 // the operations in the basic version of the algorithm |
26 val ops = List("+", "-", "*", "/", "^") |
33 val ops = List("+", "-", "*", "/", "^") |
27 |
34 |
28 def is_op(op: String) : Boolean = ops.contains(op) |
35 // (8) Implement the extended version of the shunting yard algorithm. |
|
36 // This version should properly account for the fact that the power |
|
37 // operation is right-associative. Apart from the extension to include |
|
38 // the power operation, you can make the same assumptions as in |
|
39 // basic version. |
29 |
40 |
30 def prec(op1: String, op2: String) : Boolean = assoc(op1) match { |
41 // def syard(toks: Toks, st: Toks = Nil, out: Toks = Nil) : Toks = ... |
31 case LA => precs(op1) <= precs(op2) |
|
32 case RA => precs(op1) < precs(op2) |
|
33 } |
|
34 |
|
35 def syard(toks: Toks, st: Toks = Nil, rout: Toks = Nil) : Toks = (toks, st, rout) match { |
|
36 case (Nil, _, _) => rout.reverse ::: st |
|
37 case (num::in, st, rout) if (num.forall(_.isDigit)) => |
|
38 syard(in, st, num :: rout) |
|
39 case (op1::in, op2::st, rout) if (is_op(op1) && is_op(op2) && prec(op1, op2)) => |
|
40 syard(op1::in, st, op2 :: rout) |
|
41 case (op1::in, st, rout) if (is_op(op1)) => syard(in, op1::st, rout) |
|
42 case ("("::in, st, rout) => syard(in, "("::st, rout) |
|
43 case (")"::in, op2::st, rout) => |
|
44 if (op2 == "(") syard(in, st, rout) else syard(")"::in, st, op2 :: rout) |
|
45 case (in, st, rout) => { |
|
46 println(s"in: ${in} st: ${st} rout: ${rout.reverse}") |
|
47 Nil |
|
48 } |
|
49 } |
|
50 |
|
51 def op_comp(s: String, n1: Long, n2: Long) = s match { |
|
52 case "+" => n2 + n1 |
|
53 case "-" => n2 - n1 |
|
54 case "*" => n2 * n1 |
|
55 case "/" => n2 / n1 |
|
56 case "^" => Math.pow(n2, n1).toLong |
|
57 } |
|
58 |
|
59 def compute(toks: Toks, st: List[Long] = Nil) : Long = (toks, st) match { |
|
60 case (Nil, st) => st.head |
|
61 case (op::in, n1::n2::st) if (is_op(op)) => compute(in, op_comp(op, n1, n2)::st) |
|
62 case (num::in, st) => compute(in, num.toInt::st) |
|
63 } |
|
64 |
42 |
65 |
43 |
|
44 // test cases |
|
45 // syard(split("3 + 4 * 8 / ( 5 - 1 ) ^ 2 ^ 3")) // 3 4 8 * 5 1 - 2 3 ^ ^ / + |
66 |
46 |
67 |
47 |
68 compute(syard(split("3 + 4 * ( 2 - 1 )"))) // 7 |
48 // (9) Implement a compute function that produces a Long(!) for an |
69 compute(syard(split("10 + 12 * 33"))) // 406 |
49 // input list of tokens in postfix notation. |
70 compute(syard(split("( 5 + 7 ) * 2"))) // 24 |
|
71 compute(syard(split("5 + 7 / 2"))) // 8 |
|
72 compute(syard(split("5 * 7 / 2"))) // 17 |
|
73 compute(syard(split("9 + 24 / ( 7 - 3 )"))) // 15 |
|
74 |
50 |
75 compute(syard(split("4 ^ 3 ^ 2"))) // 262144 |
51 //def compute(toks: Toks, st: List[Long] = Nil) : Long = ... |
76 compute(syard(split("4 ^ ( 3 ^ 2 )"))) // 262144 |
|
77 compute(syard(split("( 4 ^ 3 ) ^ 2"))) // 4096 |
|
78 |
52 |
79 |
53 |
80 syard(split("3 + 4 * 8 / ( 5 - 1 ) ^ 2 ^ 3")) // 3 4 8 * 5 1 - 2 3 ^ ^ / + |
54 // test cases |
81 compute(syard(split("3 + 4 * 8 / ( 5 - 1 ) ^ 2 ^ 3"))) |
55 // compute(syard(split("3 + 4 * ( 2 - 1 )"))) // 7 |
|
56 // compute(syard(split("10 + 12 * 33"))) // 406 |
|
57 // compute(syard(split("( 5 + 7 ) * 2"))) // 24 |
|
58 // compute(syard(split("5 + 7 / 2"))) // 8 |
|
59 // compute(syard(split("5 * 7 / 2"))) // 17 |
|
60 // compute(syard(split("9 + 24 / ( 7 - 3 )"))) // 15 |
|
61 // compute(syard(split("4 ^ 3 ^ 2"))) // 262144 |
|
62 // compute(syard(split("4 ^ ( 3 ^ 2 )"))) // 262144 |
|
63 // compute(syard(split("( 4 ^ 3 ) ^ 2"))) // 4096 |
|
64 // compute(syard(split("( 3 + 1 ) ^ 2 ^ 3"))) // 65536 |
82 |
65 |
83 compute(syard(split("( 3 + 1 ) ^ 2 ^ 3"))) // 65536 |
|
84 |
|
85 |
|
86 def pow(n1: Long, n2: Long) = Math.pow(n1, n2).toLong |
|