aboutsummaryrefslogtreecommitdiff
path: root/parser.php
blob: 80e01c22fc5683cf771034b5c07313ac44ea9382 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
<?php
// This file is part of Moodle - http://moodle.org/
//
// Moodle is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// Moodle is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with Moodle.  If not, see <http://www.gnu.org/licenses/>.

// Parser code for the Moodle Algebra question type
// Moodle algebra question type class
// Author: Roger Moore <rwmoore 'at' ualberta.ca>
// License: GNU Public License version 3.

defined('MOODLE_INTERNAL') || die();

/**
 * Helper function which will compare two strings using their length only.
 *
 * This function is intended for use in sorting arrays of strings by their string
 * length. This is used to order arrays for regular expressions so that the longest
 * expressions are checked first.
 * In this version, if both strings have equal length, string order is used. So this
 * version of the sort is stable.
 *
 * @param $a first string to compare
 * @param $b second string to compare
 * @return -1 if $a is longer than $b,  and +1 if $a is shorter
 */
function qtype_algebra_parser_strlen_sort($a, $b) {
    // Get the two string lengths once so we don't have to repeat the function call.
    $alen = strlen($a);
    $blen = strlen($b);
    // If the two lengths are equal use strings order.
    if ($alen == $blen) {
        return ($a > $b) ? -1 : +1;
    }
    // Otherwise return +1 if a is shorter or -1 if longer.
    return ($alen > $blen) ? -1 : +1;
}

/**
 * Base class for all the types of exception we throw.
 */
class parser_exception extends moodle_exception {
    public function __construct($error) {
        parent::__construct('exceptionmessage', 'qtype_algebra', '', $error);
    }
}
/**
 * Class which represents a single term in an algebraic expression.
 *
 * A single algebraic term is considered to be either an operation, for example addition,
 * subtraction, raising to a power etc. or something operated on, such as a number or
 * variable. Each type of term implements a subclass of this base class.
 */
class qtype_algebra_parser_term {
    // Member variables.
    public $_value;             // String of the actual term itself.
    public $_arguments = array(); // Array of arguments in class form.
    public $_formats;           // Array of format strings.
    public $_nargs;             // Number of arguments for this term.

    /**
     * Constructor for the generic parser term.
     *
     * This method is called by all subclasses to initialize the base class for use.
     * It initializes the number of arguments required, the format strings to use
     * when converting the term in various strng formats, the parser text associated
     * with the term and whether the term is one which commutes.
     *
     * @param $nargs number of arguments which this type of term requires
     * @param $formats an array of the format strings for this term keyed by type
     * @param $text the text from the expression associated with the array
     * @param $commutes if set to true then this term commutes (only for 2 argument terms)
     */
    public function __construct($nargs, $formats,  $text = '', $commutes = false) {
        $this->_value = $text;
        $this->_nargs = $nargs;
        $this->_formats = $formats;
        $this->_commutes = $commutes;
    }

    /**
     * Generates the list of arguments needed when converting the term into a string.
     *
     * This method returns an array with the arguments needed when converting the term
     * into a string. The arrys can then be used with a format string to generate the
     * string representation. The method is recursive because it needs to convert the
     * arguments of the term into strings and so it will walk down the parse tree.
     *
     * @param $method name of method to call to convert arguments into strings
     * @return array of the arguments that, with a format string, can be passed to sprintf
     */
    public function print_args($method) {
        // Create an empty array to store the arguments in.
        $args = array();
        // Handle zero argument terms differently by making the
        // first 'argument' the value of the term itself.
        if ($this->_nargs == 0) {
            $args[] = $this->_value;
        } else {
            foreach ($this->_arguments as $arg) {
                $args[] = $arg->$method();
            }
        }
        // Return the array of arguments.
        return $args;
    }

    /**
     * Produces a 'prettified' string of the expression using the standard input syntax.
     *
     * This method will use the {@link print_args} method to convert the term and all its
     * arguments into a string.
     *
     * @return string input syntax format string of the expression
     */
    public function str() {
        // First check to see if the class has been given all the arguments.
        $this->check_arguments();
        // Get an array of all the arguments except for the format string.
        $args = $this->print_args('str');
        // Insert the format string at the front of the argument array.
        array_unshift($args, $this->_formats['str']);
        // Call sprintf using the argument array as the arguments.
        return call_user_func_array('sprintf', $args);
    }

    /**
     * Produces a LaTeX formatted string of the expression.
     *
     * This method will use the {@link print_args} method to convert the term and all its
     * arguments into a LaTeX formatted string. This can then be given to the main Moodle
     * engine, with TeX filter enabled, to produce a graphical representation of the
     * expression.
     *
     * @return LaTeX format string of the expression
     */
    public function tex() {
        // First check to see if the class has been given all the arguments.
        $this->check_arguments();
        // Get an array of all the arguments except for the format string.
        $args = $this->print_args('tex');
        // Insert the format string at the front of the argument array.
        array_unshift($args, $this->_formats['tex']);
        // Call sprintf using the argument array as the arguments.
        return call_user_func_array('sprintf', $args);
    }

    /**
     * Produces a SAGE formatted string of the expression.
     *
     * This method will use the {@link print_args} method to convert the term and all its
     * arguments into a SAGE formatted string. This can then be passed to SAGE via XML-RPC
     * for symbolic comparisons. The format is very similar to the {@link str} method but
     * has all multiplications made explicit with an asterix.
     *
     * @return SAGE format string of the expression
     */
    public function sage() {
        // First check to see if the class has been given all the arguments.
        $this->check_arguments();
        // Get an array of all the arguments except for the format string.
        $args = $this->print_args('sage');
        // Insert the format string at the front of the argument array. First we
        // check to see if there is a format element called 'sage' if not then we
        // default to the standard string format.
        if (array_key_exists('sage', $this->_formats)) {
            // Insert the sage format string at the front of the argument array.
            array_unshift($args, $this->_formats['sage']);
        } else {
            // Insert the normal format string at the front of the argument array.
            array_unshift($args, $this->_formats['str']);
        }
        // Call sprintf using the argument array as the arguments.
        return call_user_func_array('sprintf', $args);
    }

    /**
     * Returns the list of arguments for the term.
     *
     * This method provides access to the arguments of the term. Although this should
     * ideally be private information it is needed in certain cases to determine
     * how neighbouring terms should display themselves.
     *
     * @return array of arguments for this term
     */
    public function arguments() {
        return $this->_arguments;
    }

    /**
     * Sets the arguments of the term to the values in the given array.
     *
     * The code here overrides the base class's method. The code uses this method to actually
     * set the arguments in the given array but a second stage to choose the format of the
     * multiplication operator is required. This is because a 'x' symbol is required when
     * multiplying two numbers. However this can be omitted when multiplying two variables,
     * a variable and a function etc.
     *
     * @param $args array to set the arguments of the term to
     */
    public function set_arguments($args) {
        if (count($args) != $this->_nargs) {
            throw new parser_exception(get_string('nargswrong', 'qtype_algebra', $this->_value));
        }
        $this->_arguments = $args;
    }

    /**
     * Checks to ensure that the correct number of arguments are defined.
     *
     * Note that this method just checks for the number or arguments it does not check
     * whether they are valid arguments. If the parameter passed is true (default value)
     * an exception will be thrown if the correct number of arguments are not present. Otherwise
     * the function returns false.
     *
     * @param $exc if true then an exception will be thrown if the number of arguments is incorrect
     * @return true if the correct number of arguments are present, false otherwise
     */
    public function check_arguments($exc = true) {
        $retval = (count($this->_arguments) == $this->_nargs);
        if ($exc && !$retval) {
            throw new parser_exception(get_string('nargswrong', 'qtype_algebra', $this->_value));
        } else {
            return $retval;
        }
    }

    /**
     * Returns a list of all the variable names found in the expression.
     *
     * This method uses the {@link collect} method to walk down the parse tree and collect
     * a list of all the variables which the parser has found in the expression. The names
     * of the variables are then returned.
     *
     * @return an array containing all the variables names in the expression
     */
    public function get_variables() {
        $list = array();
        $this->collect($list, 'qtype_algebra_parser_variable');
        return array_keys($list);
    }

    /**
     * Returns a list of all the function names found in the expression.
     *
     * This method uses the {@link collect} method to walk down the parse tree and collect
     * a list of all the functions which the parser has found in the expression. The names
     * of the functions are then returned.
     *
     * @return an array containing all the function names used in the expression
     */
    public function get_functions() {
        $list = array();
        $this->collect($list, 'qtype_algebra_parser_function');
        return array_keys($list);
    }

    /**
     * Collects all the terms of a given type with unique values in the parse tree
     *
     * This method walks recursively down the parse tree by calling itself for the arguments
     * of the current term. The method simply adds the current term to the given imput array
     * using a key set to the value of the term but only if the term matches the selected type.
     * In this way terms only a single entry per term value is return which is the functionality
     * required for the {@link get_variables} and {@link get_functions} methods.
     *
     * @param $list the array to add the term to if it matches the type
     * @param $type the name of the type of term to collect.
     * @return an array containing all the terms of the selected type keyed by their value
     */
    public function collect(&$list, $type) {
        // Add this class to the list if of the correct type.
        if (is_a($this, $type)) {
            // Add a key to the array with the value of the term, this means
            // that multiple terms with the same value will overwrite each
            // other so only one will remain.
            $list[$this->_value] = 0;
        }
        // Now loop over all the argument for this term (if any) and check them.
        foreach ($this->_arguments as $arg) {
            // Collect terms from the arguments as well.
            $arg->collect($list, $type);
        }
    }

    /**
     * Checks to see if this term is equal to another term ignoring arguments.
     *
     * This method compares the current term to another term. The default method simply compares
     * the class of each term. Terms which require more than this, for example comparing values
     * too, override this method in theor own classes.
     *
     * @param $term the term to compare to the current one
     * @return true if the terms match, false otherwise
     */
    public function equals($term) {
        // Default method just checks to ensure that the Terms are both of the same type.
        return is_a($term, get_class($this));
    }

    /**
     * Compares this term, including any arguments, with another term.
     *
     * This method uses the {@link equals} method to see if the current and given term match.
     * It then looks at any arguments which the two terms have and, recursively, calls their
     * compare methods to determine if they also match. For terms with two arguments which
     * also commute the reverse ordering of the arguments is also tried if the first order
     * fails to match.
     *
     * @param $expr top level term of an expression to compare against
     * @return true if the expressions match, false otherwise
     */
    public function equivalent($expr) {
        // Check that the argument is also a term.
        if (!is_a($expr, 'qtype_algebra_parser_term')) {
            throw new parser_exception(get_string('badequivtype', 'qtype_algebra'));
        }
        // Now check that this term is the same as the given term.
        if (!$this->equals($expr)) {
            // Terms are not equal immediately return false since the two do not match.
            return false;
        }
        // Now compare the arguments recursively...
        switch($this->_nargs) {
            case 0:
                // For zero arguments we already compared this class and found it the same so
                // because there are no arguments to check we are equivalent!
                return true;
            case 1:
                // For one argument we also need to compare the argument of each term.
                return $this->_arguments[0]->equivalent($expr->_arguments[0]);
            case 2:
                // Now it gets interesting. First we compare the two arguments in the same
                // order and see what we get...
                if ($this->_arguments[0]->equivalent($expr->_arguments[0]) and
                   $this->_arguments[1]->equivalent($expr->_arguments[1])) {
                    // Both arguments are equivalent so we have a match.
                    return true;
                } else if ($this->_commutes and $this->_arguments[0]->equivalent($expr->_arguments[1]) and
                        $this->_arguments[1]->equivalent($expr->_arguments[0])) {
                    // Otherwise if the operator commutes we can see if the first argument matches
                    // the second argument and vice versa.
                    return true;
                } else {
                    return false;
                }
            default:
                throw new parser_exception(get_string('morethantwoargs', 'qtype_algebra'));
        }
    }

    /**
     * Returns the number of arguments required by the term.
     *
     * @return the number of arguments required by the term
     */
    public function n_args() {
        return $this->_nargs;
    }

    /**
     * Evaluates the term numerically using the given variable values.
     *
     * The given parameter array is keyed by the name of the variable and the numerical
     * value to assign it is stored in the array value. This method is an abstract one
     * which must be implemented by all subclasses. Failure to do so will generate an
     * exception when the method is called.
     *
     * @param $params array of values keyed by variable name
     * @return the numerical value of the term given the provided values for the variables
     */
    public function evaluate($params) {
        throw new parser_exception(get_string('noevaluate', 'qtype_algebra', $this->_value));
    }

    /**
     * Dumps the term and its arguments to standard out.
     *
     * This method will recursively call the entire parse tree attached to it and produce
     * a nicely formatted dump of the term structure. This is mainly useful for debugging
     * purposes.
     *
     * @param $indent string containing the indentation to use
     * @param $params variable values to use if an evaluation is also desired
     * @return a string indicating the type of the term
     */
    public function dump(&$params = array(), $indent = '') {
        echo "$indent<Term type '".get_class($this).'\' with value \''.$this->_value;
        if (!empty($params)) {
            echo ' eval = \''.$this->evaluate($params)."'>\n";
        } else {
            echo "'>\n";
        }
        foreach ($this->_arguments as $arg) {
            $arg->dump($params, $indent.'  ');
        }
    }

    /**
     * Special casting operator method to convert the term object to a string.
     *
     * This is primarily a debug method. It is called when the term object is cast into a
     * string, such as happens when echoing or printing it. It simply returns a string
     * indicating the type of the parser term.
     *
     * @return a string indicating the type of the term
     */
    public function __toString() {
        return '<Algebraic parser term of type \''.get_class($this).'\'>';
    }
}

/**
 * Class representing a null, or empty, term.
 *
 * This is the type of term returned when the parser is given an empty string to parse.
 * It takes no arguments and will never be found in a parser tree. This term is solely
 * to give a valid return type for an empty string condition and so avoids the need to
 * throw an exception in such cases.
 */
class qtype_algebra_parser_nullterm extends qtype_algebra_parser_term {
    /** @var The TeX multiply operator. */
    public $id;
    /**
     * Constructs an instance of a null term.
     *
     * Initializes a null term class. Since this class represents nothing no special
     * initialization is required and no arguments are needed.
     */
    public function __construct() {
        parent::__construct(self::NARGS, self::$formats, '');
    }

    /**
     * Returns the array of arguments needed to convert this class into a string.
     *
     * Since this class is represented by an empty string which has no formatting fields
     * we override the base class method to return an empty array.
     *
     * @param $method name of method to call to convert arguments into strings
     * @return array of the arguments that, with a format string, can be passed to sprintf
     */
    public function print_args($method) {
        return array();
    }

    /**
     * Evaluates the term numerically.
     *
     * Since this is an empty term we define the evaluation as zero regardless of the parameters.
     *
     * @param $params array of the variable values to use
     */
    public function evaluate($params) {
        // Return something which is not a number.
        return acos(2.0);
    }

    // Static class properties.
    const NARGS = 0;
    private static $formats = array('str' => '',
                                  'tex' => '');
}


/**
 * Class representing a number.
 *
 * All purely numerical quantities will be represented by this type of class. There are
 * two basic types of numbers: non-exponential and exponential. Both types are handled by
 * this single class.
 */
class qtype_algebra_parser_number extends qtype_algebra_parser_term {

    /**
     * Constructs an instance of a number term.
     *
     * This function initializes an instance of a number term using the string which
     * matches the number's regular expression.
     *
     * @param $text string matching the number regular expression
     */
    public function __construct($text = '') {
        // Unfortunately PHP maths will only support a '.' as a decimal point and will not support
        // ',' as used in Danish, French etc. To allow for this we always convert any commas into
        // decimal points before we parse the string.
        $text = str_replace(',', '.', $text);
        $this->_sign = '';
        // Now determine whether this is in exponent form or just a plain number.
        if (preg_match('/([\.0-9]+)E([-+]?\d+)/', $text, $m)) {
            $this->_base = $m[1];
            $this->_exp = $m[2];
            $eformats = array('str' => '%sE%s',
                            'tex' => '%s \\' . get_config('qtype_algebra', 'multiplyoperator') . '10^{%s}');
            parent::__construct(self::NARGS, $eformats, $text);
        } else {
            $this->_base = $text;
            $this->_exp = '';
            parent::__construct(self::NARGS, self::$formats, $text);
        }
    }

    /**
     * Sets this number to be negative.
     *
     * This method will convert the number into a nagetive one. It is called when
     * the parser finds a subtraction operator in front of the number which does
     * not have a variable or another number preceding it.
     */
    public function set_negative() {
        // Prepend a minus sign to both the base and total value strings.
        $this->_base = '-'.$this->_base;
        $this->_value = '-'.$this->_value;
        $this->_sign = '-';
    }

    /**
     * Checks to see if this number is equal to another number.
     *
     * This is a two step process. First we use the base class equals method to ensure
     * that we are comparing two numbers. Then we check that the two have the same value.
     *
     * @param $expt the term to compare to the current one
     * @return true if the terms match, false otherwise
     */
    public function equals($expr) {
        // Call the default method first to check type.
        if (parent::equals($expr)) {
            return (float)$this->_value == (float)$expr->_value;
        } else {
            return false;
        }
    }

    /**
     * Generates the list of arguments needed when converting the term into a string.
     *
     * For number terms there are two possible formats: those with an exponent and those
     * without an exponent. This method determines which to use and then pushes the correct
     * arguments into the array which is returned.
     *
     * @param $method name of method to call to convert arguments into strings
     * @return array of the arguments that, with a format string, can be passed to sprintf
     */
    public function print_args($method) {
        // When displaying the number we need to worry about whether to use a decimal point
        // or a comma depending on the language currently selected/ Do this by replacing the
        // decimal point (which we have to use internally because of the PHP math standard)
        // with the correct string from the language pack.
        $base = str_replace('.', get_string('decimal', 'qtype_algebra'), $this->_base);
        // Put the base part of the number into the argument array.
        $args = array($base);
        // Check to see if we have an exponent...
        if ($this->_exp) {
            // We do so add it to the argument array as well.
            $args[] = $this->_exp;
        }
        // Return the list of arguments.
        return $args;
    }

    /**
     * Evaluates the term numerically.
     *
     * All this method does is return the string representing the number cast as a double
     * precision floating point variable.
     *
     * @param $params array of the variable values to use
     */
    public function evaluate($params) {
        return doubleval($this->_value);
    }

    // Static class properties.
    const NARGS = 0;
    private static $formats = array('str' => '%s',
                                  'tex' => '%s ');
}

/**
 * Class representing a variable term in an algebraic expression.
 *
 * When the parser finds a text string which does not correspond to a function it creates
 * this type of term and puts the contents of that text into it. Variables with names
 * corresponding to the names of the greek letters are replaced by those letters when
 * rendering the term in LaTeX. Other variables display their first letter with all
 * subsequent letters being lowercase. This reduces confusion when rendering expressions
 * consisting of multiplication of two variables.
 */
class qtype_algebra_parser_variable extends qtype_algebra_parser_term {
    // Define the list of variable names which will be replaced by greek letters.
    public static $greek = array (
        'alpha',
        'beta',
        'gamma',
        'delta',
        'epsilon',
        'zeta',
        'eta',
        'theta',
        'iota',
        'kappa',
        'lambda',
        'mu',
        'nu',
        'xi',
        'omicron',
        'pi',
        'rho',
        'sigma',
        'tau',
        'upsilon',
        'phi',
        'chi',
        'psi',
        'omega',

        'Alpha',
        'Beta',
        'Gamma',
        'Delta',
        'Epsilon',
        'Zeta',
        'Eta',
        'Theta',
        'Iota',
        'Kappa',
        'Lambda',
        'Mu',
        'Nu',
        'Xi',
        'Omicron',
        'Pi',
        'Rho',
        'Sigma',
        'Tau',
        'Upsilon',
        'Phi',
        'Chi',
        'Psi',
        'Omega',
     );

    /**
     * Constructor for an algebraic term class representing a variable.
     *
     * Initializes an instance of the variable term subclass. The method is given the text
     * in the expression corresponding to the variable name. This is then parsed to get the
     * variable name which is split into a base and subscript. If the start of the string
     * matches the name of a greek letter this is taken as the base and the remainder as the
     * subscript. Failing that either the subscript must be explicitly specified using an
     * underscore character or the first character is taken as the base.
     *
     * @param $text text matching the variable name
     */
    public function __construct($text) {
        // Create the array to store the regular expression matches in.
        $m = array();
        // Set the sign of the variable to be empty.
        $this->_sign = '';
        if (preg_match('/([^_]+)_(.*)/A', $text, $m)) {
          $this->_base = $m[1];
          $this->_subscript = $m[2];
        } else {
          $this->_base = $text;
          $this->_subscript = '';
        }
        $gmode = in_array($this->_base, self::$greek, 1) ? 'greek' : 'std';
        parent::__construct(self::NARGS, self::$formats[$gmode], $text);
    }

    /**
     * Sets this variable to be negative.
     *
     * This method will convert the number into a nagetive one. It is called when
     * the parser finds a subtraction operator in front of the number which does
     * not have a variable or another number preceding it.
     */
    public function set_negative() {
        // Set the sign to be a '-'.
        $this->_sign = '-';
    }

    /**
     * Generates the list of arguments needed when converting the term into a string.
     *
     * The string of the variable depends solely on the name and subscript and hence these
     * are the only two arguments returned in the array.
     *
     * @param $method name of method to call to convert arguments into strings
     * @return array of the arguments that, with a format string, can be passed to sprintf
     */
    public function print_args($method) {
        $under = $this->_subscript == '' ? '' : '_';
        return array($this->_sign, $this->_base, $under, $this->_subscript);
    }

    /**
     * Evaluates the number numerically.
     *
     * Overrides the base class method to simply return the numerical value of the number the
     * class represents.
     *
     * @param $params array of values keyed by variable name
     * @return the numerical value of the term given the provided values for the variables
     */
    public function evaluate($params) {
        if ($this->_sign == '-') {
            $mult = -1;
        } else {
            $mult = 1;
        }
        if (array_key_exists($this->_value, $params)) {
            return $mult * doubleval($params[$this->_value]);
        } else {
            // Found an indefined variable. Cannot evaluate numerically so throw exception.
            throw new parser_exception(get_string('undefinedvariable', 'qtype_algebra', $this->_value));
        }
    }

    /**
     * Checks to see if this variable is equal to another variable.
     *
     * This is a two step process. First we use the base class equals method to ensure
     * that we are comparing two variables. Then we check that the two are the same variable.
     *
     * @param $expr the term to compare to the current one
     * @return true if the terms match, false otherwise
     */
    public function equals($expr) {
        // Call the default method first to check type.
        if (parent::equals($expr)) {
            return $this->_value == $expr->_value and $this->_sign == $expr->_sign;
        } else {
            return false;
        }
    }

    // Static class properties.
    const NARGS = 0;
    private static $formats = array(
        'greek' => array('str' => '%s%s%s%s',
                          'tex' => '%s\%s%s{%s}'),
        'std' => array('str' => '%s%s%s%s',
                          'tex' => '%s%s%s{%s}')
    );
}


/**
 * Class representing a power operation in an algebraic expression.
 *
 * The parser creates an instance of this term when it finds a string matching the power
 * operator's syntax. The string which corresponds to the term is passed to the constructor
 * of this subclass.
 */
class qtype_algebra_parser_power extends qtype_algebra_parser_term {

    /**
     * Constructs an instance of a power operator term.
     *
     * This function initializes an instance of a power operator term using the string which
     * matches the power operator expression. Since this is simply the character representing
     * the operator it is not used except when producing a string representation of the term.
     *
     * @param $text string matching the term's regular expression
     */
    public function __construct($text) {
        parent::__construct(self::NARGS, self::$formats, $text);
    }

    /**
     * Evaluates the power operation numerically.
     *
     * Overrides the base class method to simply return the numerical value of the power
     * operation. The method evaluates the two arguments of the term and then passes them to
     * the 'pow' function from the maths library.
     *
     * @param $params array of values keyed by variable name
     * @return the numerical value of the term given the provided values for the variables
     */
    public function evaluate($params) {
        $this->check_arguments();
        return pow(doubleval($this->_arguments[0]->evaluate($params)),
                   doubleval($this->_arguments[1]->evaluate($params)));
    }

    // Static class properties.
    const NARGS = 2;
    private static $formats = array(
        'str' => '%s^%s',
        'tex' => '%s^{%s}'
    );
}


/**
 * Class representing a divide operation in an algebraic expression.
 *
 * The parser creates an instance of this term when it finds a string matching the divide
 * operator's syntax. The string which corresponds to the term is passed to the constructor
 * of this subclass.
 */
class qtype_algebra_parser_divide extends qtype_algebra_parser_term {

    /**
     * Constructs an instance of a divide operator term.
     *
     * This function initializes an instance of a divide operator term using the string which
     * matches the divide operator expression. Since this is simply the character representing
     * the operator it is not used except when producing a string representation of the term.
     *
     * @param $text string matching the term's regular expression
     */
    public function __construct($text) {
        parent::__construct(self::NARGS, self::$formats, $text);
    }

    /**
     * Evaluates the divide operation numerically.
     *
     * Overrides the base class method to simply return the numerical value of the divide
     * operation. The method evaluates the two arguments of the term and then simply divides
     * them to get the return value.
     *
     * @param $params array of values keyed by variable name
     * @return the numerical value of the term given the provided values for the variables
     */
    public function evaluate($params) {
        $this->check_arguments();
        // Get the value we are trying to divide by.
        $divby = $this->_arguments[1]->evaluate($params);
        // Check to see if this is zero.
        if ($divby == 0) {
            // Check the sign of the other argument and use to determine whether we return
            // plus or minus infinity.
            return INF * $this->_arguments[0]->evaluate($params);
        } else {
            return $this->_arguments[0]->evaluate($params) / $divby;
        }
    }

    // Static class properties.
    const NARGS = 2;
    private static $formats = array(
        'str' => '%s/%s',
        'tex' => '\\frac{%s}{%s}'
    );
}


/**
 * Class representing a multiplication operation in an algebraic expression.
 *
 * The parser creates an instance of this term when it finds a string matching the multiplication
 * operator's syntax. The string which corresponds to the term is passed to the constructor
 * of this subclass.
 */
class qtype_algebra_parser_multiply extends qtype_algebra_parser_term {

    /**
     * Constructs an instance of a multiplication operator term.
     *
     * This function initializes an instance of a multiplication operator term using the string which
     * matches the multiplication operator expression. Since this is simply the character representing
     * the operator it is not used except when producing a string representation of the term.
     *
     * @param $text string matching the term's regular expression
     */
    public function __construct($text) {
        $this->mformats = array('*' => array('str' => '%s*%s',
                                            'tex' => '%s \\' . get_config('qtype_algebra', 'multiplyoperator') . ' %s'),
                                '.' => array('str' => '%s %s',
                                            'tex' => '%s %s',
                                            'sage' => '%s*%s')
                              );
        parent::__construct(self::NARGS, $this->mformats['*'], $text, true);
    }

    /**
     * Sets the arguments of the term to the values in the given array.
     *
     * This method sets the term's arguments to those in the given array.
     *
     * @param $args array to set the arguments of the term to
     */
    public function set_arguments($args) {
        // First perform default argument setting method. This will generate
        // an error if there is a problem with the number of arguments.
        parent::set_arguments($args);
        // Set the default explicit format.
        $this->_formats = $this->mformats['*'];
        // Only allow the implicit multiplication if the second argument is either a
        // special, variable, function or bracket and not negative. In all other cases the operator must be
        // explicitly written.
        if (is_a($args[1], 'qtype_algebra_parser_bracket') or
           is_a($args[1], 'qtype_algebra_parser_variable') or
           is_a($args[1], 'qtype_algebra_parser_special') or
           is_a($args[1], 'qtype_algebra_parser_function')) {
            if (!method_exists($args[1], 'set_negative') or $args[1]->_sign == '') {
                $this->_formats = $this->mformats['.'];
            }
        }
        // Check for one more special exemption: if the second argument is a power expression
        // then we use the same criteria on the first argument of it.
        if (is_a($args[1], 'qtype_algebra_parser_power')) {
            // Get the arguments from the power term. Note we do not check these since
            // power terms are parsed before multiplication ones and are required to
            // have two arguments.
            $powargs = $args[1]->arguments();
            // Allow the implicit multiplication if the power's first argument is either a
            // special, variable, function or bracket and not negative.
            if (is_a($powargs[0], 'qtype_algebra_parser_bracket') or
               is_a($powargs[0], 'qtype_algebra_parser_variable') or
               is_a($powargs[0], 'qtype_algebra_parser_special') or
               is_a($powargs[0], 'qtype_algebra_parser_function')) {
                if (!method_exists($powargs[0], 'set_negative') or $powargs[0]->_sign == '') {
                    $this->_formats = $this->mformats['.'];
                }
            }
        }
    }

    /**
     * Evaluates the multiplication operation numerically.
     *
     * Overrides the base class method to simply return the numerical value of the multiplication
     * operation. The method evaluates the two arguments of the term and then simply multiplies
     * them to get the return value.
     *
     * @param $params array of values keyed by variable name
     * @return the numerical value of the term given the provided values for the variables
     */
    public function evaluate($params) {
        $this->check_arguments();
        return $this->_arguments[0]->evaluate($params) * $this->_arguments[1]->evaluate($params);
    }

    // Static class properties.
    const NARGS = 2;
}


/**
 * Class representing a addition operation in an algebraic expression.
 *
 * The parser creates an instance of this term when it finds a string matching the addition
 * operator's syntax. The string which corresponds to the term is passed to the constructor
 * of this subclass.
 */
class qtype_algebra_parser_add extends qtype_algebra_parser_term {

    /**
     * Constructs an instance of a addition operator term.
     *
     * This function initializes an instance of a addition operator term using the string which
     * matches the addition operator expression. Since this is simply the character representing
     * the operator it is not used except when producing a string representation of the term.
     *
     * @param $text string matching the term's regular expression
     */
    public function __construct($text) {
        parent::__construct(self::NARGS, self::$formats, $text, true);
    }

    /**
     * Evaluates the addition operation numerically.
     *
     * Overrides the base class method to simply return the numerical value of the addition
     * operation. The method evaluates the two arguments of the term and then simply adds
     * them to get the return value.
     *
     * @param $params array of values keyed by variable name
     * @return the numerical value of the term given the provided values for the variables
     */
    public function evaluate($params) {
        $this->check_arguments();
        return $this->_arguments[0]->evaluate($params) + $this->_arguments[1]->evaluate($params);
    }

    // Static class properties.
    const NARGS = 2;
    private static $formats = array(
        'str' => '%s+%s',
        'tex' => '%s + %s'
    );
}


/**
 * Class representing a subtraction operation in an algebraic expression.
 *
 * The parser creates an instance of this term when it finds a string matching the subtraction
 * operator's syntax. The string which corresponds to the term is passed to the constructor
 * of this subclass.
 */
class qtype_algebra_parser_subtract extends qtype_algebra_parser_term {

    /**
     * Constructs an instance of a subtraction operator term.
     *
     * This function initializes an instance of a subtraction operator term using the string which
     * matches the subtraction operator expression. Since this is simply the character representing
     * the operator it is not used except when producing a string representation of the term.
     *
     * @param $text string matching the term's regular expression
     */
    public function __construct($text) {
        parent::__construct(self::NARGS, self::$formats, $text);
    }

    /**
     * Evaluates the subtraction operation numerically.
     *
     * Overrides the base class method to simply return the numerical value of the subtraction
     * operation. The method evaluates the two arguments of the term and then simply subtracts
     * them to get the return value.
     *
     * @param $params array of values keyed by variable name
     * @return the numerical value of the term given the provided values for the variables
     */
    public function evaluate($params) {
        $this->check_arguments();
        return $this->_arguments[0]->evaluate($params) - $this->_arguments[1]->evaluate($params);
    }

    // Static class properties.
    const NARGS = 2;
    private static $formats = array(
        'str' => '%s-%s',
        'tex' => '%s - %s'
    );
}


/**
 * Class representing a special constant in an algebraic expression.
 *
 * The parser creates an instance of this term when it finds a string matching the a predefined
 * special constant such as pi or 'e' (from natural logarithms).
 */
class qtype_algebra_parser_special extends qtype_algebra_parser_term {

    /**
     * Constructs an instance of a special constant term.
     *
     * This function initializes an instance of a special term using the string which
     * matches the regular expression of a special constant.
     *
     * @param $text string matching a constant's regular expression
     */
    public function __construct($text) {
        parent::__construct(self::NARGS, self::$formats[$text], $text);
        $this->_sign = '';
    }

    /**
     * Sets this special to be negative.
     *
     * This method will convert the number into a nagetive one. It is called when
     * the parser finds a subtraction operator in front of the number which does
     * not have a variable or another number preceding it.
     */
    public function set_negative() {
        // Set the sign to be a '-'.
        $this->_sign = '-';
    }

    /**
     * Evaluates the special constant numerically.
     *
     * Overrides the base class method to simply return the numerical value of the special
     * constant which is defined by an internal switch based on the constant's name.
     *
     * @param $params array of values keyed by variable name
     * @return int the numerical value of the term given the provided values for the variables
     */
    public function evaluate($params) {
        if ($this->_sign == '-') {
            $mult = -1;
        } else {
            $mult = 1;
        }
        switch($this->_value) {
            case 'pi':
                return $mult * pi();
            case 'e':
                return $mult * exp(1);
            default:
                return 0;
        }
    }

    /**
     * Returns the array of arguments needed to convert this special term into a string.
     *
     * The special term generally has a fixed, predefined formatting already hard coded so
     * the only remaining variable is the sign of the term and this is what this method
     * returns.
     *
     * @param $method name of method to call to convert arguments into strings
     * @return array of the arguments that, with a format string, can be passed to sprintf
     */
    public function print_args($method) {
        return array($this->_sign);
    }

    /**
     * Checks to see if this constant is equal to another term.
     *
     * This is a two step process. First we use the base class equals method to ensure
     * that we are comparing two variables. Then we check that the two are the same constant.
     *
     * @param $expr the term to compare to the current one
     * @return true if the terms match, false otherwise
     */
    public function equals($expr) {
        // Call the default method first to check type.
        if (parent::equals($expr)) {
            return $this->_value == $expr->_value and $this->_sign == $expr->_sign;
        } else {
            return false;
        }
    }

    // Static class properties.
    const NARGS = 0;
    private static $formats = array(
        'pi' => array(  'str' => '%spi',
                         'tex' => '%s\\pi'),
        'e' => array(  'str' => '%se',
                         'tex' => '%se')
    );
}

/**
 * implement math functions that aren't php builtins
 */
function log2($arg)
{
    return log($arg, 2);
}

function ln($arg)
{
    return log($arg);
}

/**
 * Class representing a function in an algebraic expression.
 *
 * The parser creates an instance of this term when it finds a string matching the function's
 * syntax. The string which corresponds to the term is passed to the constructor
 * of this subclass.
 */
class qtype_algebra_parser_function extends qtype_algebra_parser_term {

    /**
     * Constructs an instance of a function term.
     *
     * This function initializes an instance of a function term using the string which
     * matches the name of a function.
     *
     * @param $text string matching the function's regular expression
     */
    public function __construct($text) {
        if ($text == 'log') {
            throw new parser_exception(get_string('deprecatedlog', 'qtype_algebra'));
        }
        if (!function_exists($text) and !array_key_exists($text, self::$fnmap)) {
            throw new parser_exception(get_string('undefinedfunction', 'qtype_algebra', $text));
        }
        $formats = array( 'str' => '%s'.$text.'%s');
        if (array_key_exists($text, self::$texmap)) {
            $formats['tex'] = '%s'.self::$texmap[$text].' %s';
        } else {
            $formats['tex'] = '%s\\'.$text.' %s';
        }
        $this->_sign = '';
        parent::__construct(self::NARGS, $formats, $text);
    }

    /**
     * Sets this function to be negative.
     *
     * This method will convert the function into a negative one. It is called when
     * the parser finds a subtraction operator in front of the function which does
     * not have a variable or another number preceding it e.g. 3*-sin(x)
     */
    public function set_negative() {
        // Set the sign to be a '-'.
        $this->_sign = '-';
    }

    /**
     * Sets the arguments of the term to the values in the given array.
     *
     * The code here overrides the base class's method. The code uses this method to actually
     * set the arguments in the given array but a second stage to insert brackets around the
     * function's argument is required.
     *
     * @param $args array to set the arguments of the term to
     */
    public function set_arguments($args) {
        if (count($args) != $this->_nargs) {
            throw new parser_exception(get_string('badfuncargs', 'qtype_algebra', $this->_value));
        }
        if (!is_a($args[0], 'qtype_algebra_parser_bracket')) {
            // Check to see if this function requires a special bracket.
            if (in_array($this->_value, self::$bracketmap)) {
                $b = new qtype_algebra_parser_bracket('<');
            } else {
                // Does not require special brackets so create normal ones.
                $b = new qtype_algebra_parser_bracket('(');
            }
            $b->set_arguments($args);
            $this->_arguments = array($b);
        } else {
            // First term already a bracket.
            // Check to see if we need a special bracket.
            if (in_array($this->_value, self::$bracketmap)) {
                // Make the bracket special.
                $args[0]->make_special();
            }
            // Set the arguments to the given type.
            $this->_arguments = $args;
        }
    }

    /**
     * Generates the list of arguments needed when converting the term into a string.
     *
     * The string of the function depends solely on the function argument and the sign.
     * The name has already been coded in at construction time.
     *
     * @param $method name of method to call to convert arguments into strings
     * @return array of the arguments that, with a format string, can be passed to sprintf
     */
    public function print_args($method) {
        // First ensure that there are the correct number of arguments.
        $this->check_arguments();
        return array($this->_sign, $this->_arguments[0]->$method());
    }

    /**
     * Evaluates the function numerically.
     *
     * Overrides the base class method to simply return the numerical value of the function.
     * Each function name is first checked against an internal map to determine the corresponding
     * PHP math function to call. If the function is not in the map it is assumed to already be
     * the correct name for a PHP math function.
     *
     * @param $params array of values keyed by variable name
     * @return the numerical value of the term given the provided values for the variables
     */
    public function evaluate($params) {
        // First ensure that there are the correct number of arguments.
        $this->check_arguments();
        // Get the correct sign to multiply the value by.
        if ($this->_sign == '-') {
            $mult = -1;
        } else {
            $mult = 1;
        }
        // Check to see if there is an entry to map the function name to a PHP function.
        if (array_key_exists($this->_value, self::$fnmap)) {
            $func = self::$fnmap[$this->_value];
            return $mult * $func($this->_arguments[0]->evaluate($params));
        } else {
            // No map entry so the function name must already be a PHP function...
            $tmp = $this->_value;
            return $mult * $tmp($this->_arguments[0]->evaluate($params));
        }
    }

    /**
     * Checks to see if this function is equal to another term.
     *
     * This is a two step process. First we use the base class equals method to ensure
     * that we are comparing two variables. Then we check that the two are the same constant.
     *
     * @param $expr the term to compare to the current one
     * @return true if the terms match, false otherwise
     */
    public function equals($expr) {
        // Call the default method first to check type.
        if (parent::equals($expr)) {
            return $this->_value == $expr->_value and $this->_sign == $expr->_sign;
        } else {
            return false;
        }
    }

    // Static class properties.
    const NARGS = 1;
     /* fnmap is not needed, since all needed
      *   functions are implemented without pseudonyms
      */
    public static $fnmap = array ();
    public static $texmap = array('sqrt'  => '\\sqrt',
                                  'log2'  => '\\log_{2}',
                                  'log10' => '\\log_{10}',
                                  'asin'  => '\\sin^{-1}',
                                  'acos'  => '\\cos^{-1}',
                                  'atan'  => '\\tan^{-1}',
                                  'asinh' => '\\sinh^{-1}',
                                  'acosh' => '\\cosh^{-1}',
                                  'atanh' => '\\tanh^{-1}',
                                  );

    // List of functions requiring special brackets.
    public static $bracketmap = array ('sqrt'
                                       );
}


/**
 * Class representing a bracket operation in an algebraic expression.
 *
 * The parser creates an instance of this term when it finds a string matching the bracket
 * operator's syntax. The string which corresponds to the term is passed to the constructor
 * of this subclass. Note that a pair of brackets is treated as a single term. There are no
 * separate open and close bracket operators.
 */
class qtype_algebra_parser_bracket extends qtype_algebra_parser_term {

    public function __construct($text) {
        parent::__construct(self::NARGS, self::$formats[$text], $text);
        $this->_sign = '';
        $this->_open = $text;
        switch($this->_open) {
            case '(':
                $this->_close = ')';
                break;
            case '[':
                $this->_close = ']';
                break;
            case '{':
                $this->_close = '}';
                break;
            // Special kind of bracket. This behaves as normal brackets for a string but as invisible
            // curly brackets '{}' with LaTeX.
            case '<':
                $this->_close = '>';
                break;
        }
    }

    /**
     * Evaluates the bracket operation numerically.
     *
     * Overrides the base class method to simply return the numerical value of the bracket
     * operation. The method evaluates the argument of the term, i.e. what is inside the
     * brackets, and then returns the value.
     *
     * @param $params array of values keyed by variable name
     * @return the numerical value of the term given the provided values for the variables
     */
    public function evaluate($params) {
        if ($this->_sign == '-') {
            $mult = -1;
        } else {
            $mult = 1;
        }
        if (count($this->_arguments) != $this->_nargs) {
            return 0;
        }
        return $mult * $this->_arguments[0]->evaluate($params);
    }

    public function set_negative() {
        // Set the sign to be a '-'.
        $this->_sign = '-';
    }

    /**
     * Set the bracket type to 'special'.
     *
     * The method converts the bracket to the special type. The special type appears as a
     * normal bracket in string mode but produces the invisible curly brackets for LaTeX.
     */
    public function make_special() {
        $this->_open = '<';
        $this->_close = '>';
        // Call the base class constructor as if this were a new instance of the bracket.
        parent::__construct(self::NARGS, self::$formats['<'], '<');
    }

    // Member variables.
    public $_open = '(';
    public $_close = ')';

    // Static class properties.
    const NARGS = 1;
    private static $formats = array(
        '(' => array('str' => '%s(%s)',
                      'tex' => '%s\\left( %s \\right)'),
        '[' => array('str' => '%s[%s]',
                      'tex' => '%s\\left[ %s \\right]'),
        '{' => array('str' => '%s{%s}',
                      'tex' => '%s\\left\\lbrace %s \\right\\rbrace'),
        '<' => array('str' => '%s(%s)',
                      'tex' => '%s{%s}')
    );

    public function print_args($method) {
        $args = array($this->_sign);
        foreach ($this->_arguments as $arg) {
            $args[] = $arg->$method();
        }
        // Return the array of arguments.
        return $args;
    }
}



/**
 * The main parser class.
 *
 * This class implements the methods needed to parse an expression. It uses a series of
 * regular expressions to indentify the different terms in the expression and then creates
 * instances of the correct subclass to handle them.
 */
class qtype_algebra_parser {
    // Special constants which the parser will understand.
    public static $specials = array (
        'pi',
        'e'
    );

    // Functions which the parser will understand.
    // You have to implement any that are not standard PHP math functions.
    public static $functions = array ('sqrt',
                                      'exp',
                                      'log2',
                                      'ln',
                                      'log',
                                      'log10',
                                      'sinh',
                                      'cosh',
                                      'tanh',
                                      'sin',
                                      'cos',
                                      'tan',
                                      'asin',
                                      'acos',
                                      'atan',
                                      'asinh',
                                      'acosh',
                                      'atanh',
                                      );

    // Array to define the priority of the different operations. The parser implements the standard BODMAS priority:
    // brackets, order (power), division, mulitplication, addition, subtraction.
    private static $priority = array (
        array('qtype_algebra_parser_power'),
        array('qtype_algebra_parser_function'),
        array('qtype_algebra_parser_divide', 'qtype_algebra_parser_multiply'),
        array('qtype_algebra_parser_add', 'qtype_algebra_parser_subtract')
    );

    // Regular experssion to match an open bracket.
    private static $openb = '/[\{\(\[]/A';
    // Regular experssion to match a close bracket.
    private static $closeb = '/[\}\)\]]/A';
    // Regular expression to match a plain float or integer number without exponent.
    private static $plainnumber = '(([0-9]+(\.|,)[0-9]*)|([0-9]+)|((\.|,)[0-9]+))';
    // Regular expression to match a float or integer number with an exponent.
    private static $expnumber = '(([0-9]+(\.|,)[0-9]*)|([0-9]+)|((\.|,)[0-9]+))E([-+]?\d+)';
    // Array to associate close brackets with the correct open bracket type.
    private static $bramap = array(')' => '(', ']' => '[', '}' => '{');

    /**
     * Constructor for the main parser class.
     *
     * This constructor initializes the token map of the main parser class. It constructs a map of
     * regular expressions to class types. As it parses a string it uses these regular expressions to
     * find tokens in the input string which are then fed to the corresponding term class for
     * interpretation.
     */
    public function __construct() {
        $this->_tokens = array (
            array ('/(\^|\*\*)/A',                            'qtype_algebra_parser_power'    )
            , array ('/\//A',                                 'qtype_algebra_parser_divide'   )
            , array ('/\*/A',                                   'qtype_algebra_parser_multiply' )
            , array ('/\+/A',                                   'qtype_algebra_parser_add'      )
            , array ('/-/A',                                    'qtype_algebra_parser_subtract' )
            , array ('/('.self::$expnumber.'|'.self::$plainnumber.')/A',    'qtype_algebra_parser_number'   )
            , array ('/[A-Za-z][A-Za-z0-9_]*/A',                'qtype_algebra_parser_identifier' )
            );
    }

    /**
     * Parses a given string containing an algebric expression and returns the corresponding parse tree.
     *
     * This method loops over the string using the regular expressions in the token map to break down the
     * string into tokens. These tokens are arranged into a structured stack, taking account of the
     * bracket structure. Finally then method calls the {@link interpret} method to convert the structured
     * token strings into a fully parsed term structure. The method can optionally be passed a list of
     * variables which are used in the expression. If such a list is passed then the parser will attempt
     * to match the current position in the string with one of these given variables before any other
     * token. When passing a variable list a third parameter allows a choice of whether to allow additional
     * undeclared variables. This defaults to false when a list of variables is passed and is ignored otherwise.
     *
     * @param $text string containing the expression to parse
     * @param $variables array containing known variable names
     * @param $undecvars whether to allow (true) undeclared variable names
     * @return top term of the parsed expression
     */
    public function parse($text, $variables = array(), $undecvars = false) {
        $i = 0;
        // Create an array to store the parse tree.
        $tree = array();
        // Create an array to act as a temporary storage stack. This stack is used to
        // push higher levels of the parse tree as it is assembled from the expression.
        $stack = array();
        // Array used to store the match results from regular expression searches.
        $m = array();
        // Loop over the expression string moving along it using the offset variable $i while
        // there are still characters left to parse.
        while ($i < strlen($text)) {
            // Match any white space at the start of the string and 'remove' it by advancing
            // the pointer by the length of the string matching the regular expression white
            // space pattern.
            if (preg_match('/\s+/A', substr($text, $i), $m)) {
                $i += strlen($m[0]);
                // Return to the start of the loop in case this was white space characters at
                // the end of the string.
                continue;
            }
            // Since we don't have any white space the first thing we look for (top priority)
            // are open brackets.
            if (preg_match(self::$openb, substr($text, $i), $m)) {
                // Check for a non-operator and if one is found assume implicit multiplication.
                if (count($tree) > 0 and (is_array($tree[count($tree) - 1]) or
                    (is_object($tree[count($tree) - 1])
                     and $tree[count($tree) - 1]->n_args() == 0))) {
                    // Make the implicit assumption explicit by adding an appropriate
                    // multiplication operator.
                    array_push($tree, new qtype_algebra_parser_multiply('*'));
                }
                // Push the current parse tree onto the stack.
                array_push($stack, $tree);
                // Create a new parse tree starting with a bracket term.
                $tree = array(new qtype_algebra_parser_bracket($m[0]));
                // Increment the string pointer by the length of the string that was matched.
                $i += strlen($m[0]);
                // Return to the start of the loop.
                continue;
            }
            // Now see if we have a close bracket here.
            if (preg_match(self::$closeb, substr($text, $i), $m)) {
                // First check that the current parse tree has at least one term.
                if (count($tree) == 0) {
                    throw new parser_exception(get_string('badclosebracket', 'qtype_algebra'));
                }
                // Now check that the current tree started with a bracket.
                if (!is_a($tree[0], 'qtype_algebra_parser_bracket')) {
                    throw new parser_exception(get_string('mismatchedcloseb', 'qtype_algebra'));
                } else if ($tree[0]->_value != self::$bramap[$m[0]]) {
                    // Check that the open and close bracket are of the same type.
                    throw new parser_exception(get_string('mismatchedbracket', 'qtype_algebra', $tree[0]->_value.$m[0]));
                }
                // Append the current tree to the tree one level up on the stack.
                array_push($stack[count($stack) - 1], $tree);
                // The new tree is the lowest level tree on the stack so we
                // pop the new tree off the stack.
                $tree = array_pop($stack);
                $i += strlen($m[0]);
                continue;
            }
            // Here we have not found any open or close brackets or known variables so we can
            // parse the string for a normal token.
            foreach ($this->_tokens as $token) {
                if (preg_match($token[0], substr($text, $i), $m)) {
                    if ($token[1] == 'qtype_algebra_parser_identifier') {
                      if (in_array($m[0], self::$functions, 1)) {
                        $token[1] = 'qtype_algebra_parser_function';
                      }
                      else if (in_array($m[0], self::$specials, 1)) {
                        $token[1] = 'qtype_algebra_parser_special';
                      }
                      else if (in_array($m[0], $variables, 1)) {
                        $token[1] = 'qtype_algebra_parser_variable';
                      } else {
                        if (!empty($variables) and !$undecvars) {
                          throw new parser_exception(get_string('undeclaredvar', 'qtype_algebra', $m[0]));
                        }
                        // heretofore unknown identifier, promote to variable:
                        $token[1] = 'qtype_algebra_parser_variable';
                      }
                    }

                    // Check for a zero argument term preceding a variable, function or special and then
                    // add the implicit multiplication.
                    if (count($tree) > 0 and ($token[1] == 'qtype_algebra_parser_variable' or
                        $token[1] == 'qtype_algebra_parser_function' or
                        $token[1] == 'qtype_algebra_parser_special')
                        and (is_array($tree[count($tree) - 1]) or
                        $tree[count($tree) - 1]->n_args() == 0)) {
                        array_push($tree, new qtype_algebra_parser_multiply('*'));
                    }
                    $i += strlen($m[0]);
                    array_push($tree, new $token[1]($m[0]));
                    continue 2;
                }
            }
            throw new parser_exception(get_string('unknownterm', 'qtype_algebra', substr($text, $i)));
        } // End while loop over tokens.
        // If all the open brackets have been closed then the stack will be empty and the
        // tree will contain the entire parsed expression.
        if (count($stack) > 0) {
            throw new parser_exception(get_string('mismatchedopenb', 'qtype_algebra'));
        }
        return $this->interpret($tree);
    }

    /**
     * Takes a structured token map and converts it into a parsed term structure.
     *
     * This is an internal method of the parser class and is called by the {@link parse}
     * method. It performs the final stage of the parsing process and returns the fully
     * parsed term structure.
     *
     * @param $tree structured token array
     * @return top term of the fully parsed structure
     */
    public function interpret($tree) {
        // First check to see if we are passed anything at all. If not then simply
        // return a qtype_algebra_parser_nullterm.
        if (count($tree) == 0) {
            return new qtype_algebra_parser_nullterm;
        }
        // Now we check to see if this tree is inside brackets. If so then
        // we remove the bracket object from the tree and store it in a
        // temporary variable. We will then parse the remainder of the tree
        // and make the top level term the bracket's argument if applicable.
        if (is_a($tree[0], 'qtype_algebra_parser_bracket')) {
            $bracket = array_splice($tree, 0, 1);
            $bracket = $bracket[0];
        } else {
            $bracket = '';
        }
        // Next we loop over the tree and look for arrays. These represent
        // brackets inside our tree and so we need to process them first.
        for ($i = 0; $i < count($tree); $i++) {
            // Check for a list type if we find one then replace
            // it with the interpreted term.
            if (is_array($tree[$i])) {
                $tree[$i] = $this->interpret($tree[$i]);
            }
        }
        // The next job is to check the subtraction operations to determine whether they are
        // really subtraction operations or whether they are minus signs for negative numbers.
        $toremove = array();
        for ($i = 0; $i < count($tree); $i++) {
            // Check that this element is an addition or subtraction operator.
            if (is_a($tree[$i], 'qtype_algebra_parser_subtract') or is_a($tree[$i], 'qtype_algebra_parser_add')) {
                // Check whether the precedding argument (if there is one) is a number or
                // a variable. In either case this is a addition/subtraction operation so we continue.
                if ($i > 0 and (is_a($tree[$i - 1], 'qtype_algebra_parser_variable') or
                             is_a($tree[$i - 1], 'qtype_algebra_parser_number') or
                             is_a($tree[$i - 1], 'qtype_algebra_parser_bracket'))) {
                    continue;
                } else {
                    // Otherwise we have found a minus sign indicating a positive or negative quantity...
                    // Check that we do have a number following otherwise generate an exception...
                    if ($i == (count($tree) - 1) or !method_exists($tree[$i + 1], 'set_negative')) {
                        throw new parser_exception(get_string('illegalplusminus', 'qtype_algebra'));
                    }
                    // If we have a subtract operation then we need to make the following number negative.
                    if (is_a($tree[$i], 'qtype_algebra_parser_subtract')) {
                        // Set the number to be negative.
                        $tree[$i + 1]->set_negative();
                    }
                    // Add the term to the removal list.
                    $toremove[$i] = 1;
                }
            }
        }
        // Remove the elements from the tree who's keys are found in the removal list.
        $tree = array_diff_key($tree, $toremove);
        // Re-key the tree array so that the keys are sequential.
        $tree = array_values($tree);
        foreach (self::$priority as $ops) {
            $i = 0;
            while ($i < count($tree)) {
                if (in_array(get_class($tree[$i]), $ops)) {
                    if ($tree[$i]->n_args() == 1) {
                        if (($i + 1) < count($tree)) {
                            $tree[$i]->set_arguments(array_splice($tree, $i + 1, 1));
                            $i++;
                            continue;
                        } else {
                            throw new parser_exception(get_string('missingonearg', 'qtype_algebra', $tree[$i]->_value));
                        }
                    } else if ($tree[$i]->n_args() == 2) {
                        if ($i > 0 and $i < (count($tree) - 1)) {
                            $tree[$i]->set_arguments(array($tree[$i - 1],
                                                    $tree[$i + 1]));
                            array_splice($tree, $i + 1, 1);
                            array_splice($tree, $i - 1, 1);
                            continue;
                        } else {
                            throw new parser_exception(get_string('missingtwoargs', 'qtype_algebra', $tree[$i]->_value));
                        }
                    }
                } else {
                    $i++;
                }
            }
        }
        // If there are no terms in the parse tree then we were passed an empty string
        // in which case we create a null term and return it.
        if (count($tree) == 0) {
            return new qtype_algebra_parser_nullterm;
        } else if (count($tree) != 1) {
            throw new parser_exception(get_string('notopterm', 'qtype_algebra'));
        }
        if ($bracket) {
            $bracket->set_arguments(array($tree[0]));
            return $bracket;
        } else {
            return $tree[0];
        }
    }
}