equal
deleted
inserted
replaced
1 // Shunting Yard Algorithm |
1 // Shunting Yard Algorithm |
2 // including Associativity for Operators |
2 // including Associativity for Operators |
3 // ===================================== |
3 // ===================================== |
|
4 |
|
5 object CW9b { |
|
6 |
4 |
7 |
5 // type of tokens |
8 // type of tokens |
6 type Toks = List[String] |
9 type Toks = List[String] |
7 |
10 |
8 // helper function for splitting strings into tokens |
11 // helper function for splitting strings into tokens |
30 "^" -> 4) |
33 "^" -> 4) |
31 |
34 |
32 // the operations in the basic version of the algorithm |
35 // the operations in the basic version of the algorithm |
33 val ops = List("+", "-", "*", "/", "^") |
36 val ops = List("+", "-", "*", "/", "^") |
34 |
37 |
35 // (8) Implement the extended version of the shunting yard algorithm. |
38 // (3) Implement the extended version of the shunting yard algorithm. |
36 // This version should properly account for the fact that the power |
39 // This version should properly account for the fact that the power |
37 // operation is right-associative. Apart from the extension to include |
40 // operation is right-associative. Apart from the extension to include |
38 // the power operation, you can make the same assumptions as in |
41 // the power operation, you can make the same assumptions as in |
39 // basic version. |
42 // basic version. |
40 |
43 |
43 |
46 |
44 // test cases |
47 // test cases |
45 // syard(split("3 + 4 * 8 / ( 5 - 1 ) ^ 2 ^ 3")) // 3 4 8 * 5 1 - 2 3 ^ ^ / + |
48 // syard(split("3 + 4 * 8 / ( 5 - 1 ) ^ 2 ^ 3")) // 3 4 8 * 5 1 - 2 3 ^ ^ / + |
46 |
49 |
47 |
50 |
48 // (9) Implement a compute function that produces a Long(!) for an |
51 // (4) Implement a compute function that produces a Long(!) for an |
49 // input list of tokens in postfix notation. |
52 // input list of tokens in postfix notation. |
50 |
53 |
51 //def compute(toks: Toks, st: List[Long] = Nil) : Long = ... |
54 //def compute(toks: Toks, st: List[Long] = Nil) : Long = ... |
52 |
55 |
53 |
56 |
61 // compute(syard(split("4 ^ 3 ^ 2"))) // 262144 |
64 // compute(syard(split("4 ^ 3 ^ 2"))) // 262144 |
62 // compute(syard(split("4 ^ ( 3 ^ 2 )"))) // 262144 |
65 // compute(syard(split("4 ^ ( 3 ^ 2 )"))) // 262144 |
63 // compute(syard(split("( 4 ^ 3 ) ^ 2"))) // 4096 |
66 // compute(syard(split("( 4 ^ 3 ) ^ 2"))) // 4096 |
64 // compute(syard(split("( 3 + 1 ) ^ 2 ^ 3"))) // 65536 |
67 // compute(syard(split("( 3 + 1 ) ^ 2 ^ 3"))) // 65536 |
65 |
68 |
|
69 } |