author | Christian Urban <christian.urban@kcl.ac.uk> |
Sun, 15 Sep 2024 12:57:59 +0100 | |
changeset 493 | 244df77507c2 |
parent 428 | cdfa6a293453 |
permissions | -rw-r--r-- |
220 | 1 |
// Shunting Yard Algorithm |
2 |
// including Associativity for Operators |
|
3 |
// ===================================== |
|
219 | 4 |
|
396 | 5 |
object C3b { |
288 | 6 |
|
7 |
||
220 | 8 |
// type of tokens |
219 | 9 |
type Toks = List[String] |
10 |
||
220 | 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 |
|
219 | 18 |
|
19 |
||
220 | 20 |
// power is right-associative, |
21 |
// everything else is left-associative |
|
219 | 22 |
def assoc(s: String) : Assoc = s match { |
23 |
case "^" => RA |
|
24 |
case _ => LA |
|
25 |
} |
|
26 |
||
27 |
||
220 | 28 |
// the precedences of the operators |
219 | 29 |
val precs = Map("+" -> 1, |
220 | 30 |
"-" -> 1, |
31 |
"*" -> 2, |
|
32 |
"/" -> 2, |
|
33 |
"^" -> 4) |
|
219 | 34 |
|
220 | 35 |
// the operations in the basic version of the algorithm |
219 | 36 |
val ops = List("+", "-", "*", "/", "^") |
37 |
||
428
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
396
diff
changeset
|
38 |
// ADD YOUR CODE BELOW |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
396
diff
changeset
|
39 |
//====================== |
219 | 40 |
|
428
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
396
diff
changeset
|
41 |
|
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
396
diff
changeset
|
42 |
|
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
396
diff
changeset
|
43 |
// (3) |
346 | 44 |
def syard(toks: Toks, st: Toks = Nil, out: Toks = Nil) : Toks = ??? |
220 | 45 |
|
219 | 46 |
|
220 | 47 |
// test cases |
48 |
// syard(split("3 + 4 * 8 / ( 5 - 1 ) ^ 2 ^ 3")) // 3 4 8 * 5 1 - 2 3 ^ ^ / + |
|
219 | 49 |
|
50 |
||
428
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
396
diff
changeset
|
51 |
// (4) |
346 | 52 |
def compute(toks: Toks, st: List[Int] = Nil) : Int = ??? |
219 | 53 |
|
54 |
||
220 | 55 |
// test cases |
56 |
// compute(syard(split("3 + 4 * ( 2 - 1 )"))) // 7 |
|
57 |
// compute(syard(split("10 + 12 * 33"))) // 406 |
|
58 |
// compute(syard(split("( 5 + 7 ) * 2"))) // 24 |
|
59 |
// compute(syard(split("5 + 7 / 2"))) // 8 |
|
60 |
// compute(syard(split("5 * 7 / 2"))) // 17 |
|
61 |
// compute(syard(split("9 + 24 / ( 7 - 3 )"))) // 15 |
|
62 |
// compute(syard(split("4 ^ 3 ^ 2"))) // 262144 |
|
63 |
// compute(syard(split("4 ^ ( 3 ^ 2 )"))) // 262144 |
|
64 |
// compute(syard(split("( 4 ^ 3 ) ^ 2"))) // 4096 |
|
65 |
// compute(syard(split("( 3 + 1 ) ^ 2 ^ 3"))) // 65536 |
|
219 | 66 |
|
288 | 67 |
} |