How to calculate multi-operator of list in dart?

Question

I have a list of num and string of operator above:

final List<dynamic> items = [5.0, "-", 2, "*", 3];

I want to calculate the value inside of it. I can do like this:

  final List<dynamic> items = [5.0, "-", 2, "*", 3]; //correct is -1
  num result = 0;
  String op = "+";
  for (final item in items) {
    if (item is String) {
      op = item;
    }
    if (item is num) {
      switch (op) {
        case "+":
          result = result + item;
          break;
        case "-":
          result = result - item;
          break;
        case "*":
          result = result * item;
          break;
        case "/":
          result = result / item;
          break;
      }
    }
  }
  print(result); // incorrect result: 9

As above code, If it is just an "+" or "-" operator it would return the correct answer, but because of the order of operators "/" and "*" doing like above return incorrect result.

Can anyone suggest any algorithm?

Answer 1

Here is one way of doing it, the code works but I didn't put the tests that would be necessary to check for bad input.

// functions for basic operations
num multiply(num leftOp, num rightOp) => leftOp * rightOp;
num divide(num leftOp, num rightOp) => leftOp / rightOp;
num add(num leftOp, num rightOp) => leftOp + rightOp;
num substract(num leftOp, num rightOp) => leftOp - rightOp;

void main() {
  final List<dynamic> items = [
    2,
    "*",
    5,
    "/",
    2,
    "-",
    3,
    "+",
    8
  ]; //correct is 10

  num result = 0;

  // Copy the list in a temporary list
  var calc = [...items];

  // set the precedence order of the operators
  // create 2 groups of equal importance
  var operators = [
    {
      "*": multiply,
      "/": divide,
    },
    {
      "+": add,
      "-": substract,
    }
  ];

  // loop until all operators have produced result
  while (calc.length > 1) {
    for (var opPrecedence in operators) {
      // find first operator in a group, starting from left

      var pos = 0;

      do {
        pos = calc.indexWhere((e) => opPrecedence.containsKey(e));

        if (pos >= 0) {
          num leftOp = calc[pos - 1];
          num rightOp = calc[pos + 1];

          var operation = opPrecedence[calc[pos]];

          result = operation!(leftOp, rightOp);

          // remove the 2 operands and replace with result
          calc.removeAt(pos);
          calc.removeAt(pos);
          calc[pos - 1] = result;
        }
      } while (pos >= 0);
    }
  }

  // what should be left is the final result
  print(calc[0]);
}

Answer 2

You can create your own simple calculator parser for this purpose and use it.
Building (generation) of the parser will take less than one second.
You can always modify it to suit your needs and generate an updated parser.
Below is an example of definition such a parser.
It contains (also for example) a value calculation for your data (as an expression).

This script will generate a parser into example/calculator.dart.

File tool/calculator_builder.dart:

import 'package:parser_builder/branch.dart';
import 'package:parser_builder/bytes.dart';
import 'package:parser_builder/char_class.dart';
import 'package:parser_builder/character.dart';
import 'package:parser_builder/combinator.dart';
import 'package:parser_builder/error.dart';
import 'package:parser_builder/expression.dart';
import 'package:parser_builder/fast_build.dart';
import 'package:parser_builder/parser_builder.dart';
import 'package:parser_builder/sequence.dart';

Future<void> main(List<String> args) async {
  final context = Context();
  return fastBuild(context, [_parse, _expression_], 'example/calculator.dart',
      header: __header, publish: {'parse': _parse});
}

const __header = '''
import 'package:source_span/source_span.dart';
import 'package:tuple/tuple.dart';

void main() {
  final List items = [5.0, "-", 2, "*", 3];
  final source = items.join(' ');
  final result = parse(source);
  print(result);
}

num _calculate(num left, String operator, num right) {
  switch (operator) {
    case '+':
      return left + right;
    case '-':
      return left - right;
    case '*':
      return left * right;
    case '/':
      return left / right;
    case '~/':
      return left ~/ right;
    default:
      throw StateError('Unknown operator: \$operator');
  }
}
''';

const _additive = Named(
    '_additive',
    BinaryExpression(
        _multiplicative, _additiveOperator, _multiplicative, _calculate));

const _additiveOperator =
    Named('_additiveOperator', Terminated(Tags(['+', '-']), _ws));

const _calculate = ExpressionAction<num>(
    ['left', 'op', 'right'], '_calculate({{left}}, {{op}}, {{right}})');

const _closeParen = Named('_closeParen', Terminated(Tag(')'), _ws));

const _decimal = Named(
    '_decimal',
    Terminated(
        Map1(
            Recognize(
              Tuple3(Digit1(), Tag('.'), Digit1()),
            ),
            ExpressionAction<num>(['x'], 'num.parse({{x}})')),
        _ws));

const _expression = Ref<String, num>('_expression');

const _expression_ = Named('_expression', _additive);

const _integer = Named(
    '_integer',
    Terminated(
        Map1(Digit1(), ExpressionAction<num>(['x'], 'int.parse({{x}})')), _ws));

const _isWhitespace = CharClass('#x9 | #xA | #xD | #x20');

const _multiplicative = Named('_multiplicative',
    BinaryExpression(_primary, _multiplicativeOperator, _primary, _calculate));

const _multiplicativeOperator =
    Named('_multiplicativeOperator', Terminated(Tags(['*', '/', '~/']), _ws));

const _openParen = Named('_openParen', Terminated(Tag('('), _ws));

const _parse = Named('_parse', Delimited(_ws, _expression, Eof<String>()));

const _primary = Named(
    '_primary',
    Nested(
        'expression',
        Alt3(
          _decimal,
          _integer,
          Delimited(_openParen, _expression, _closeParen),
        )));

const _ws = Named('_ws', SkipWhile(_isWhitespace));

If you run example/calculator.dart you will get the result.

-1.0

You can modify the build script and generate it as a library (eg as lib/calculator.dart).
Then import this library and use it.

It requires some programming skills from you, but there is nothing difficult about it.
Everything is very simple.

Answer 3

By combined ManuH68 answer I did:

void main() {
test('Return correct', () {
const correctResult = 10;
final calc = <dynamic>[2, "*", 5, "/", 2, "-", 3, "+", 8];
num result = 0;

// clean "*" and "/" first
while (calc.contains("*") || calc.contains("/")) {
  final pos = calc.indexWhere((e) => e == "*" || e == "/");
  num leftOp = calc[pos - 1];
  num rightOp = calc[pos + 1];
  switch (calc[pos]) {
    case "*":
      result = leftOp * rightOp;
      break;
    case "/":
      result = leftOp / rightOp;
      break;
  }
  calc.removeAt(pos);
  calc.removeAt(pos);
  calc[pos - 1] = result;
}

// Then After calculated "*" and "/" perform calculate on "+" and "-"
while (calc.length > 1) {
  final pos = calc.indexWhere((e) => e == "-" || e == "+");
  num leftOp = calc[pos - 1];
  num rightOp = calc[pos + 1];
  switch (calc[pos]) {
    case "-":
      result = leftOp - rightOp;
      break;
    case "+":
      result = leftOp + rightOp;
      break;
  }
  calc.removeAt(pos);
  calc.removeAt(pos);
  calc[pos - 1] = result;
}

  expect(calc[0], correctResult);
});
}

this might not clean but this is what I founded that work