|
1 // Shunting Yard Algorithm |
|
2 // including Associativity for Operators |
|
3 // ===================================== |
|
4 |
|
5 object CW8b { |
|
6 |
|
7 |
|
8 // type of tokens |
|
9 type Toks = List[String] |
|
10 |
|
11 // helper function for splitting strings into tokens |
|
12 def split(s: String) : Toks = s.split(" ").toList |
|
13 |
|
14 // left- and right-associativity |
|
15 abstract class Assoc |
|
16 case object LA extends Assoc |
|
17 case object RA extends Assoc |
|
18 |
|
19 |
|
20 // power is right-associative, |
|
21 // everything else is left-associative |
|
22 def assoc(s: String) : Assoc = s match { |
|
23 case "^" => RA |
|
24 case _ => LA |
|
25 } |
|
26 |
|
27 |
|
28 // the precedences of the operators |
|
29 val precs = Map("+" -> 1, |
|
30 "-" -> 1, |
|
31 "*" -> 2, |
|
32 "/" -> 2, |
|
33 "^" -> 4) |
|
34 |
|
35 // the operations in the basic version of the algorithm |
|
36 val ops = List("+", "-", "*", "/", "^") |
|
37 |
|
38 // (3) Implement the extended version of the shunting yard algorithm. |
|
39 // This version should properly account for the fact that the power |
|
40 // operation is right-associative. Apart from the extension to include |
|
41 // the power operation, you can make the same assumptions as in |
|
42 // basic version. |
|
43 |
|
44 def syard(toks: Toks, st: Toks = Nil, out: Toks = Nil) : Toks = ??? |
|
45 |
|
46 |
|
47 // test cases |
|
48 // syard(split("3 + 4 * 8 / ( 5 - 1 ) ^ 2 ^ 3")) // 3 4 8 * 5 1 - 2 3 ^ ^ / + |
|
49 |
|
50 |
|
51 // (4) Implement a compute function that produces an Int for an |
|
52 // input list of tokens in postfix notation. |
|
53 |
|
54 def compute(toks: Toks, st: List[Int] = Nil) : Int = ??? |
|
55 |
|
56 |
|
57 // test cases |
|
58 // compute(syard(split("3 + 4 * ( 2 - 1 )"))) // 7 |
|
59 // compute(syard(split("10 + 12 * 33"))) // 406 |
|
60 // compute(syard(split("( 5 + 7 ) * 2"))) // 24 |
|
61 // compute(syard(split("5 + 7 / 2"))) // 8 |
|
62 // compute(syard(split("5 * 7 / 2"))) // 17 |
|
63 // compute(syard(split("9 + 24 / ( 7 - 3 )"))) // 15 |
|
64 // compute(syard(split("4 ^ 3 ^ 2"))) // 262144 |
|
65 // compute(syard(split("4 ^ ( 3 ^ 2 )"))) // 262144 |
|
66 // compute(syard(split("( 4 ^ 3 ) ^ 2"))) // 4096 |
|
67 // compute(syard(split("( 3 + 1 ) ^ 2 ^ 3"))) // 65536 |
|
68 |
|
69 } |