Line data    Source code

       1             : // RPN(Reverse Polish Notation) expression
       2             : import 'dart:math';
       3             : import 'package:logger/logger.dart';
       4             : 
       5           9 : var log = Logger(
       6           3 :   printer: SimplePrinter(printTime: true),
       7             : );
       8             : 
       9             : abstract class RPN<N> {
      10             :   List<String> expression = [];
      11             :   List<N> stack = [];
      12             : 
      13           2 :   void fromString(String input, String delim) {
      14           4 :     expression = input.split(delim);
      15             :   }
      16             : 
      17             :   // for Infix Notation
      18             :   Map<String, String> braces = {
      19             :     ")": "(",
      20             :     "}": "{",
      21             :     "]": "[",
      22             :   };
      23             : 
      24             :   Map<String, int> opcodes = {
      25             :     "S-": 1,
      26             :     "S+": 1,
      27             :     "S!": 1,
      28             :     "*": 2,
      29             :     "/": 2,
      30             :     "%": 2,
      31             :     "×": 2,
      32             :     "÷": 2,
      33             :     "+": 3,
      34             :     "-": 3,
      35             :     "<<": 4,
      36             :     ">>": 4,
      37             :     "&": 5,
      38             :     "^": 6,
      39             :     "|": 7,
      40             :   };
      41             : 
      42           3 :   void fromInfixString(String input, RegExp number, [RegExp? func]) {
      43             :     // load infix notation string to rev polish notation
      44          18 :     var opcodeLength = opcodes.keys.map((x) => x.length).reduce(max);
      45           3 :     List<String> p = [];
      46           3 :     List<MapEntry<String, int>> s = [];
      47             :     int idx = 0;
      48             :     bool single = true;
      49           6 :     while (idx < input.length) {
      50             :       // skip space
      51           3 :       var rest0 = input.substring(idx);
      52           3 :       var rest = rest0.trimLeft();
      53          12 :       idx += rest0.length - rest.length;
      54             : 
      55           9 :       log.d("p=$p, s=$s");
      56           9 :       log.d("rest: idx=$idx, $rest");
      57             :       var oplen = 0;
      58             :       var prio = 100;
      59             :       String? opnum;
      60           3 :       var isnum = number.matchAsPrefix(rest);
      61           3 :       var isfunc = func?.matchAsPrefix(rest);
      62             :       if (isnum != null) {
      63             :         // number
      64           3 :         opnum = isnum[0]!;
      65           3 :         oplen = opnum.length;
      66             :         prio = 0;
      67             :         single = false;
      68           9 :         log.d("number: $opnum len=$oplen prio=$prio");
      69          18 :       } else if (braces.containsValue(rest[0]) || braces.containsKey(rest[0])) {
      70             :         // braces
      71             :         oplen = 1;
      72           2 :         opnum = rest[0];
      73             :         prio = 100;
      74           6 :         single = braces.containsValue(rest[0]);
      75           6 :         log.d("brace: $opnum len=$oplen prio=$prio");
      76             :       } else if (isfunc != null) {
      77             :         // func
      78           1 :         opnum = isfunc[0]!;
      79           1 :         oplen = opnum.length;
      80             :         prio = 0;
      81             :         single = false;
      82           3 :         log.d("func: $opnum len=$oplen prio=$prio");
      83             :       } else {
      84             :         // opcode
      85          12 :         for (int x = min(opcodeLength, rest.length); x != 0; x--) {
      86           3 :           var op = rest.substring(0, x);
      87             :           if (single) {
      88           2 :             op = "S$op";
      89             :           }
      90           6 :           if (opcodes.containsKey(op)) {
      91             :             opnum = op;
      92             :             oplen = x;
      93           6 :             prio = opcodes[op]!;
      94             :             single = true;
      95           9 :             log.d("opcode: $opnum len=$oplen prio=$prio");
      96             :             break;
      97             :           }
      98             :         }
      99             :       }
     100             :       if (opnum == null) {
     101           0 :         log.e("error: cannot find op/num: idx=$idx, rest=$rest");
     102             :         break;
     103             :       }
     104           6 :       if (braces.containsValue(opnum)) {
     105           6 :         log.d("brace-start push: $opnum");
     106           4 :         s.add(MapEntry(opnum, prio));
     107           6 :       } else if (braces.containsKey(opnum)) {
     108           4 :         log.d("brace-end move");
     109           4 :         var sbrace = braces[opnum]!;
     110           6 :         while (s.last.key != sbrace) {
     111           2 :           var tmp = s.removeLast();
     112          12 :           if (braces.containsKey(tmp.key) || braces.containsValue(tmp.key)) {
     113           0 :             log.d("brace skip move: $tmp");
     114             :           } else {
     115           6 :             log.d("brace move: $tmp");
     116           4 :             p.add(tmp.key);
     117             :           }
     118             :         }
     119           6 :         if (s.last.key == sbrace) {
     120             :           // pop sbrace
     121           2 :           s.removeLast();
     122             :         }
     123             :       } else {
     124          12 :         while (s.isNotEmpty && s.last.value <= prio) {
     125          15 :           log.d("notempty=${s.isNotEmpty}, lastval=${s.last}");
     126           3 :           var tmp = s.removeLast();
     127          18 :           if (braces.containsKey(tmp.key) || braces.containsValue(tmp.key)) {
     128           0 :             log.d("move: brace skip: $tmp");
     129             :           } else {
     130           9 :             log.d("move: $tmp");
     131           6 :             p.add(tmp.key);
     132             :           }
     133             :         }
     134          12 :         log.d("finished: notempty=${s.isNotEmpty}");
     135           3 :         if (s.isNotEmpty) {
     136          12 :           log.d("finished: lastval=${s.last}");
     137             :         }
     138           6 :         s.add(MapEntry(opnum, prio));
     139             :       }
     140           3 :       idx += oplen;
     141             :     }
     142           3 :     while (s.isNotEmpty) {
     143           3 :       var tmp = s.removeLast();
     144          18 :       if (braces.containsKey(tmp.key) || braces.containsValue(tmp.key)) {
     145           0 :         log.d("last move: brace skip: $tmp");
     146             :       } else {
     147           9 :         log.d("last move: $tmp");
     148           6 :         p.add(tmp.key);
     149             :       }
     150             :     }
     151           9 :     log.d("result: $input -> $p");
     152           3 :     expression = p;
     153             :   }
     154             : 
     155           3 :   N? pop() {
     156           6 :     if (stack.isEmpty) {
     157             :       return null;
     158             :     }
     159           6 :     return stack.removeLast();
     160             :   }
     161             : 
     162           3 :   void push(N v) {
     163           6 :     stack.add(v);
     164             :   }
     165             : 
     166             :   void exec1(String v);
     167             : 
     168           3 :   N? evaluate() {
     169           6 :     for (var x in expression) {
     170           3 :       exec1(x);
     171             :     }
     172           6 :     if (stack.isEmpty) {
     173             :       return null;
     174             :     }
     175           6 :     return stack.last;
     176             :   }
     177             : }