Daily Challenge #10 - Calculator

We're back with another code challenge, this one comes from user obrok on Codewars:

Create a simple calculator that given a string of operators (+ - * and /) and numbers separated by spaces returns the value of that expression

Example:

Calculator().evaluate("2 / 2 + 3 * 4 - 6") # => 7

Remember about the order of operations! Multiplications and divisions have a higher priority and should be performed left-to-right. Additions and subtractions have a lower priority and should also be performed left-to-right.

Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Comments

[Mikhail Korolev]

Alright, I'm gonna be the one who posts this.

const calc = exp => eval(exp)

[Alvaro Montoro]

If you add a check to verify the string is well formed, this will probably be the best and simplest answer.

[Yozen Hernandez]

Similarly unfair, the solution in R:

calc <- function (expr) {
    eval(parse(text=expr))
}

> calc("2 / 2 + 3 * 4 - 6")
[1] 7

Warning: don't do this.

[Alvaro Montoro]

JavaScript

const calculator = operation => {

  // verify that the string with the operation has the right format:
  //   - a number
  //   - optionally followed by 0 or more:
  //       - a space
  //       - an operator (+-*/)
  //       - a space
  //       - another number
  if (!operation.match(/^\d+( [\+\-\/\*] \d+)*$/)) return null;

  // easy solution: now that we know the string has the format that we expect, 
  // return (eval(operation));
  // ...but someone did it already, so let's go the long way :P


  // break the string by spaces
  let ops = operation.split(" ");
  let opsSimple = [];

  // multiplication and division take priority
  // we create a new array that will only have numbers and + or -
  for (x = 0; x < ops.length; x++) {
    if (ops[x] === '*') {
      const val = opsSimple.pop();
      opsSimple.push(val * ops[x+1]);
      x++;
    } else if (ops[x] === '/') {
      // do not allow division by zero!
      if (ops[x+1] === "0") return "Error! Division by zero!";
      const val = opsSimple.pop();
      opsSimple.push(val / ops[x+1]);
      x++;
    } else {
      opsSimple.push(ops[x]);
    }
  }

  // calculate the addtiions and substractions sequentially
  let result = parseInt(opsSimple[0]);
  for (x = 1; x < opsSimple.length; x = x + 2) {
    if (opsSimple[x] === '+') {
      result += opsSimple[x+1];
    } else {
      result -= opsSimple[x+1];
    }
  }

  return result;
}

Live demo on CodePen

[Alvaro Montoro]

10 out of 10 challenges! :)

Although I was just able to make 2 using CSS only :-/

[Corey Alexander]

I'm gonna try to keep doing em each day in July if I can, you game lol?

I'm currently a day behind you since I didn't get this one done yesterday

[Alvaro Montoro]

Let's do it!

[Dave Jacoby]

#!/usr/bin/env perl

use strict ;
use warnings ;
use feature qw{ say postderef signatures state } ;
no warnings qw{ experimental::postderef experimental::signatures } ;

use Carp ;

my $string = "2 / 2 + 3 * 4 - 6" ;
say evaluate( $string ) ;
exit ;

sub evaluate( $string) {
        # multiplication
        while ( $string =~ m/(\-?\d+ \* \-?\d+)/ ) {
            my $before = $1 ;
            my ( $i, $j ) = $before =~ m{(\-?\d+)}g ;
            my $k = $i * $j ;
            $string =~ s/\Q$before/$k/mx ;
            }

        # division
        while ( $string =~ m/(\-?\d+ \/ \-?\d+)/ ) {
            my $before = $1 ;
            my ( $i, $j ) = $before =~ m{(\-?\d+)}g ;
            croak 'Divide by zero' if $j == 0;
            my $k = $i / $j ;
            $string =~ s/\Q$before/$k/mx ;
            }

        # addition
        while ( $string =~ m/(\-?\d+ \+ \-?\d+)/ ) {
            my $before = $1 ;
            my ( $i, $j ) = $before =~ m{(\-?\d+)}g ;
            my $k = $i + $j ;
            $string =~ s/\Q$before/$k/mx ;
            }

        # subtraction
        while ( $string =~ m/(\-?\d+ \- \-?\d+)/ ) {
            my $before = $1 ;
            my ( $i, $j ) = $before =~ m{(\-?\d+)}g ;
            my $k = $i - $j ;
            $string =~ s/\Q$before/$k/mx ;
            }

    return $string ;
    }

[Dave Jacoby]

And, I see now that I don't handle non-whole-numbers, which the problem doesn't give me, but could come along anyway. "5 / 4", for example.

And that's entirely a regex problem.

Hrm.

[Dave Jacoby]

Regex was -?\d+, which would handle whole numbers, but with division in the mix, you have to handle the possibility of decimals.

The regex became -?\d+(?:\.\d+)?. (?: indicates it's not matching, so we're not grabbing the fractional aspect independently, \.\d_ matches one dot and however many digits, and )? closes the thing and matches only if found, so that it doesn't have to be a floating point number.

#!/usr/bin/env perl

use strict ;
use warnings ;
use feature qw{ say postderef signatures state } ;
no warnings qw{ experimental::postderef experimental::signatures } ;

use Carp ;

my $string = "2 / 2 + 3 * 4 - 6" ;
say evaluate( $string ) ;
exit ;

# Remember MDAS
sub evaluate( $string) {
        while ( $string =~ m/(-?\d+(?:\.\d+)? \* -?\d+(?:\.\d+)?)/ ) {
            my $before = $1 ;
            my ( $i, $j ) = $before =~ m{(-?\d+(?:\.\d+)?)}g ;
            my $k = $i * $j ;
            $string =~ s/\Q$before/$k/mx ;
            }

        while ( $string =~ m/(-?\d+(?:\.\d+)? \/ -?\d+(?:\.\d+)?)/ ) {
            my $before = $1 ;
            my ( $i, $j ) = $before =~ m{(-?\d+(?:\.\d+)?)}g ;
            exit if $j == 0;
            my $k = $i / $j ;
            $string =~ s/\Q$before/$k/mx ;
            }

        while ( $string =~ m/(-?\d+(?:\.\d+)? \+ -?\d+(?:\.\d+)?)/ ) {
            my $before = $1 ;
            my ( $i, $j ) = $before =~ m{(-?\d+(?:\.\d+)?)}g ;
            my $k = $i + $j ;
            $string =~ s/\Q$before/$k/mx ;
            }

        while ( $string =~ m/(-?\d+(?:\.\d+)? \- \?\d+(?:\.\d+)?)/ ) {
            my $before = $1 ;
            my ( $i, $j ) = $before =~ m{(-?\d+(?:\.\d+)?)}g ;
            my $k = $i - $j ;
            $string =~ s/\Q$before/$k/mx ;
            }

    return $string ;
    }

[Ben Lovy]

Rust, verbosely:

use std::{
    ops::{Add, Div, Mul, Sub},
    str::FromStr,
};

macro_rules! apply_op {
    ($op:ident, $tokens:ident, $idx:ident) => {{
        $tokens[$idx - 1] =
            Token::Num($tokens[$idx - 1].as_num()?.$op($tokens[$idx + 1].as_num()?));
        $tokens.remove($idx + 1);
        $tokens.remove($idx);
    }};
}

#[derive(Debug)]
enum CalcError {
    Op,
    Input,
}

#[derive(Debug, Clone, Copy, PartialEq)]
enum Op {
    Add,
    Sub,
    Mul,
    Div,
}

impl FromStr for Op {
    type Err = CalcError;

    fn from_str(s: &str) -> Result<Self, Self::Err> {
        match s {
            "+" => Ok(Op::Add),
            "-" => Ok(Op::Sub),
            "*" => Ok(Op::Mul),
            "/" => Ok(Op::Div),
            _ => Err(CalcError::Input),
        }
    }
}

#[derive(Debug, Clone, Copy, PartialEq)]
enum Token {
    Num(i64),
    Op(Op),
}

impl Token {
    fn as_num(&mut self) -> Result<i64, CalcError> {
        match self {
            Token::Num(x) => Ok(*x),
            _ => Err(CalcError::Op),
        }
    }
}

impl FromStr for Token {
    type Err = CalcError;

    fn from_str(s: &str) -> Result<Self, Self::Err> {
        if let Ok(x) = s.parse::<i64>() {
            return Ok(Token::Num(x));
        } else {
            let op = Op::from_str(s)?;
            return Ok(Token::Op(op));
        }
    }
}

fn eval_str(s: &str) -> Result<i64, CalcError> {
    let mut tokens = tokenize(s)?;

    let mut i = 0;

    // do mul/div
    loop {
        // check if there are any
        let ops: Vec<&Token> = tokens
            .iter()
            .filter(|e| **e == Token::Op(Op::Div) || **e == Token::Op(Op::Mul))
            .collect();
        if ops.is_empty() {
            break;
        }

        if let Some(token) = tokens.get(i) {
            if let Token::Op(op) = *token {
                match op {
                    Op::Div => apply_op!(div, tokens, i),
                    Op::Mul => apply_op!(mul, tokens, i),
                    _ => {}
                }
            }
            i += 1;
        } else {
            // start again from the top
            i = 0;
        }
    }

    i = 0;
    // do add/sub
    loop {
        // check if there are any
        let ops: Vec<&Token> = tokens
            .iter()
            .filter(|e| **e == Token::Op(Op::Add) || **e == Token::Op(Op::Sub))
            .collect();
        if ops.is_empty() {
            break;
        }
        if let Some(token) = tokens.get(i) {
            if let Token::Op(op) = *token {
                match op {
                    Op::Add => apply_op!(add, tokens, i),
                    Op::Sub => apply_op!(sub, tokens, i),
                    _ => {}
                }
            }
            i += 1;
        } else {
            // start again from the top
            i = 0;
        }
    }

    // should only be one token left, return it
    Ok(tokens[0].as_num()?)
}

// string to token Vec
fn tokenize(s: &str) -> Result<Vec<Token>, CalcError> {
    let mut ret = Vec::new();
    for c in s.split(' ') {
        ret.push(Token::from_str(c)?);
    }
    Ok(ret)
}

fn main() {
    let input = "2 / 2 + 3 * 4 - 6";
    assert_eq!(eval_str(input).unwrap(), 7);
}

[Corey Alexander]

Oh macro_rules are something I haven't dug into and explored much yet! Definitely used the built in ones, but haven't written any yet.
Thanks for the example!

[Ben Lovy]

I was intimidated by them for a while and avoided the topic - tried one once and now they even end up in my daily puzzle solutions :P Truly not complicated to use, and super handy!

[Ben Lovy]

Haskell:

import Data.Char (isDigit)

data Token = Num Int | Add | Sub | Mul | Div deriving (Eq, Show)

input :: String
input = "2 / 2 + 3 * 4 - 6"

tokenize :: String -> [String]
tokenize s = filter (/= " ") $ map (:[]) s

parse :: [String] -> [Token]
parse [] = []
parse (t:ts)
    | isDigit $ t !! 0 = Num (read t) : parse ts
    | t == "*" = Mul : parse ts
    | t == "/" = Div : parse ts
    | t == "+" = Add : parse ts
    | t == "-" = Sub : parse ts
    | otherwise = parse ts

division :: [Token] -> [Token]
division [] = []
division [a] = [a]
division (t:ts) =
    case t of
        Num x ->
            case head ts of
                Div ->
                    let
                        (Num y) = head $ tail ts
                    in
                        Num (quot x y) : division (tail $ tail ts)
                _ -> t : division ts
        _ -> t : division ts

multiplication :: [Token] -> [Token]
multiplication [] = []
multiplication [a] = [a]
multiplication (t:ts) =
    case t of
        Num x ->
            case head ts of
                Mul ->
                    let
                        (Num y) = head $ tail ts
                    in
                        Num (x * y) : multiplication (tail $ tail ts)
                _ -> t : multiplication ts
        _ -> t : multiplication ts

addition :: [Token] -> [Token]
addition [] = []
addition [a] = [a]
addition (t:ts) =
    case t of
        Num x ->
            case head ts of
                Add ->
                    let
                        (Num y) = head $ tail ts
                    in
                        Num (x + y) : addition (tail $ tail ts)
                _ -> t : addition ts
        _ -> t : addition ts

subtraction :: [Token] -> [Token]
subtraction [] = []
subtraction [a] = [a]
subtraction (t:ts) =
    case t of
        Num x ->
            case head ts of
                Sub ->
                    let
                        (Num y) = head $ tail ts
                    in
                        Num (x - y) : subtraction (tail $ tail ts)
                _ -> t : subtraction ts
        _ -> t : subtraction ts

evalStr :: String -> Int
evalStr s =
    let
        [(Num x)] = subtraction $ addition $ multiplication $ division $ parse $ tokenize s
    in
        x

Would anyone be able to help me abstract out that operation pattern? I'm a little stumped on how to de-duplicate this code, even though Haskell is great at that.

[Dave Jacoby]

I recall this from Data Structures, and that there's ambiguity between handle from left and PEMDAS, which is a huge argument for Reverse Polish Notation.

[Dave Jacoby]

For context (and an example I'm hitting in my testing), 4 - 6 - 2. By PEMDAS, they're of equal order, but it really depends on if you want (4 - 6) - 2 == -4 or 4 - (6 - 2) == 0.

With RPN, it's always number number operator, and variations on that are how we get precedence.

4 6 2 - - has 6 2 - in number number operator form and thus becomes 4, simplifying to 4 4 - and then 0.

4 6 - 2 - would get you the 4 6 - first, giving -2, then -2 2 -, which is -4`

Not that I do my regular math like this...

[Olivier “Ölbaum” Scherler]

I’m (still) learning Erlang. This is my solution with the given operators and integer numbers. I’m quite satisfied:

-module( calc ).
-export( [ calc/1 ] ).

-include_lib("eunit/include/eunit.hrl").

% expr := term [+|- term]*
% term := factor [*|/ factor]*
% factor := number
% number := -?digit+

skip_ws( [ $\  | Rest ] ) ->
    skip_ws (Rest );
skip_ws( [ $\t | Rest ] ) ->
    skip_ws (Rest );
skip_ws( Rest ) ->
    Rest.

parse_number( [ $- | S ] ) ->
    parse_number( S, undef, -1 );
parse_number( S ) ->
    parse_number( S, undef, 1 ).

parse_number( [ C | Rest ], Value, Sign ) when C >= $0, C =< $9 ->
    NewValue = case Value of
        undef -> 0;
        _ -> Value
    end * 10 + ( C - $0 ),
    parse_number( Rest, NewValue, Sign );
parse_number( Rest, Value, Sign ) ->
    case Value of
        undef -> { invalid, "" };
        _ -> { Sign * Value, Rest }
    end.

parse_factor( S ) ->
    parse_number( S ).

parse_term( S ) ->
    parse_term( S, 1, $* ).

parse_term( S, Value, Op ) ->
    { F1, R1 } = parse_factor( S ),

    NewValue = case Op of
        $* -> Value * F1;
        $/ -> Value / F1
    end,

    R2 = skip_ws( R1 ),
    case R2 of
        [ $* | R3 ] -> parse_term( skip_ws( R3 ), NewValue, $* );
        [ $/ | R3 ] -> parse_term( skip_ws( R3 ), NewValue, $/ );
        _ -> { NewValue, R2 }
    end.

parse_expr( S ) ->
    parse_expr( S, 0, $+ ).

parse_expr( S, Value, Op ) ->
    { F1, R1 } = parse_term( S ),

    NewValue = case Op of
        $+ -> Value + F1;
        $- -> Value - F1
    end,

    R2 = skip_ws( R1 ),
    case R2 of
        [ $+ | R3 ] -> parse_expr( skip_ws( R3 ), NewValue, $+ );
        [ $- | R3 ] -> parse_expr( skip_ws( R3 ), NewValue, $- );
        _ -> { NewValue, R2 }
    end.

calc( S ) ->
    { Result, [] } = parse_expr( skip_ws( S ) ),
    Result.

% TESTS

skip_ws_test_() -> [
    ?_assertEqual( "", skip_ws("") ),
    ?_assertEqual( "", skip_ws(" ") ),
    ?_assertEqual( "", skip_ws("  ") ),
    ?_assertEqual( "", skip_ws( [ $\t ] ) ),
    ?_assertEqual( "ASDF", skip_ws("  ASDF") ),
    ?_assertEqual( "AS DF ", skip_ws( [ $\ , $\t, $\ , $\ , $A, $S, $\ , $D, $F, $\  ] ) )
].

parse_number_test_() -> [
    ?_assertEqual( { 0, "" }, parse_number("0") ),
    ?_assertEqual( { 2, "" }, parse_number("2") ),
    ?_assertEqual( { 42, "" }, parse_number("42") ),
    ?_assertEqual( { -1, "" }, parse_number("-1") ),
    ?_assertEqual( { -145, "" }, parse_number("-145") ),
    ?_assertEqual( { -145, " some stuff" }, parse_number("-145 some stuff") ),
    ?_assertEqual( { invalid, "" }, parse_number("asdf") ),
    ?_assertEqual( { invalid, "" }, parse_number("-") ),
    ?_assertEqual( { invalid, "" }, parse_number("-stuff") ),
    ?_assertEqual( { invalid, "" }, parse_number("- stuff") )
].

parse_term_test_() -> [
    ?_assertEqual( { 6, "" }, parse_term("3 * 2") ),
    ?_assertEqual( { -6, "" }, parse_term("-3 * 2") ),
    ?_assertEqual( { -6, "" }, parse_term("3 * -2") ),
    ?_assertEqual( { 6, "" }, parse_term("-3 * -2") )
].

parse_expr_test_() -> [
    ?_assertEqual( { 5, "" }, parse_expr("3 + 2") ),
    ?_assertEqual( { 1, "" }, parse_expr("3 - 2") ),
    ?_assertEqual( { 1, "" }, parse_expr("3 + -2") ),
    ?_assertEqual( { -1, "" }, parse_expr("-3 - -2") )
].

calc_test_() -> [
    ?_assertEqual( 0, calc("0") ),
    ?_assertEqual( 2, calc("2") ),
    ?_assertEqual( -3, calc("-3") ),
    ?_assertEqual( 128, calc("128  ") ),
    ?_assertEqual( 128, calc(" 128  ") ),
    ?_assertEqual( 14, calc("2 + 3 * 4") ),
    ?_assertEqual( 9.0, calc("6 / 2 * 3") ),
    ?_assertEqual( 1, calc("-1 - -2") ),
    ?_assertEqual( 11, calc("3 * -2 + 17") )
].

To run it:

% erl
1> c(calc).
{ok,calc}
2> calc:test().
  All 33 tests passed.
ok
3> calc:calc("2 + 3 * 4").
14
4> calc:calc("8 / 2 * 4").
16.0

Then I extended it with:

• floating point numbers;
• exponent notation (125e-2 = 1.25);
• powers, with ^;
• parentheses.

You can find it in this Gist, and try it:

% erl
1> c(calc).
{ok,calc}
2> calc:test().
  All 57 tests passed.
ok
3> calc:calc("1.5 * 2").
3.0
4> calc:calc("12e4 * 2e-3").
240.0
5> calc:calc("3 ^ 4").
81.0
6> calc:calc("2 ^ 0.5").
1.4142135623730951
7> calc:calc("2 + ( 3 * 4 )").
14.0
8> calc:calc("8 / 2 * (2 + 2)").
16.0 % OBVIOUSLY!
9> calc:calc("3^(1/2)").
1.7320508075688772

parse_number got a bit out of hand, but I find the rest quite elegant. I like Erlang.

[Dylan Paulus]

Nim.

from strutils import split, parseFloat
from sequtils import foldl, map
import re

type CalcKind = enum
  vkOperator
  vkValue

type
  CalcItem = ref object
    case Kind: CalcKind
    of vkOperator: Operator: string
    of vkValue: Value: float

proc toCalcItem(item: string): CalcItem =
  if item.match(re"\d+"): 
    return CalcItem(Kind: CalcKind.vkValue, Value: parseFloat(item))

  return CalcItem(Kind: CalcKind.vkOperator, Operator: item)

proc calculate(input: string): float =
  var stack: seq[CalcItem] = input.split(" ").map(toCalcItem)
  var backStack: seq[CalcItem]

  while len(stack) > 0:
    let item = stack.pop()

    if item.Kind == CalcKind.vkOperator:
      if item.Operator == "*":
        let curr = backStack.pop()
        let other = stack.pop()
        backStack.add(CalcItem(Kind: CalcKind.vkValue, Value: other.Value * curr.Value))
      elif item.Operator == "/":
        let curr = backStack.pop()
        let other = stack.pop()
        backStack.add(CalcItem(Kind: CalcKind.vkValue, Value: other.Value / curr.Value))
      else:
        backStack.add(item)
    else:
      backStack.add(item)

  while len(backStack) > 2:
    let curr = backStack.pop()
    let operator = backStack.pop()
    let other = backStack.pop()

    if operator.Operator == "+":
      backStack.add(CalcItem(Kind: CalcKind.vkValue, Value: curr.Value + other.Value))
    else:
      backStack.add(CalcItem(Kind: CalcKind.vkValue, Value: curr.Value - curr.Value))

  return foldl(backStack, a + b.Value, 0.0)


when isMainModule:
  echo $calculate("2 / 2 + 3 * 4 - 6") #7

[Dylan Paulus]

Did some cleanup using types. No more string->float->string conversions. Adding old solution below!

from strutils import split, parseFloat
from sequtils import foldl

proc calculate(input: string): float =
  var stack: seq[string] = input.split(" ")
  var backStack: seq[string]

  while len(stack) > 0:
    let item = stack.pop()

    if item == "*":
      let curr = parseFloat(backStack.pop())
      let other = parseFloat(stack.pop())
      backStack.add($(other * curr))
    elif item == "/":
      let curr = parseFloat(backStack.pop())
      let other = parseFloat(stack.pop())
      backStack.add($(other / curr))
    else:
      backStack.add(item)

  while len(backStack) > 2:
    let item = parseFloat(backStack.pop())
    let operator = backStack.pop()
    let other = parseFloat(backStack.pop())

    if operator == "+":
      backStack.add($(item + other))
    else:
      backStack.add($(item - other))

  return foldl(backStack, a + parseFloat(b), 0.0)


when isMainModule:
  echo $calculate("2 / 2 + 3 * 4 - 6") #7

[K.V.Harish]

My solution in js

calculator = () => {
  return {
    evaluate: (str) => {
      try{
        return eval(str)
      }
      catch(error) {
        return 'Invalid expression'
      }
    }
  } 
}

calculator().evaluate('2 / 2 + 3 * 4 - 6') // 7
calculator().evaluate('2 / 2 + ') // Invalid expression

[Kevin Sullivan]

interface Number {
  type: "NUMBER" | string;
  value: number;
}

interface Operation {
  type: "OPERATION";
  value: "*" | "/" | "+" | "-";
}

const OPERATIONS = {
  "*": multiply,
  "/": divide,
  "+": add,
  "-": subtract
} as const;

const parse = (input: string): (Operation | Number)[] =>
  input
    .split(" ")
    .map(
      (input: string): Number | Operation =>
        input === "*"
          ? { type: "OPERATION", value: "*" }
          : input === "/"
          ? { type: "OPERATION", value: "/" }
          : input === "+"
          ? { type: "OPERATION", value: "+" }
          : input === "-"
          ? { type: "OPERATION", value: "-" }
          : { type: "NUMBER", value: Number(input) }
    );

export const combine = ({ value }: Operation, a: Number, b: Number) => ({
  type: "NUMBER",
  value: OPERATIONS[value](a.value, b.value)
});

export const doOperations = (operations: ("*" | "/" | "+" | "-")[]) => (
  input: (Operation | Number)[]
) => {
  let result = input;

  const firstOperationIndex = (list: (Operation | Number)[]) =>
    list.findIndex(
      ({ type, value }) =>
        type === "OPERATION" && operations.includes(value as any)
    );

  const operationsRemaining = (result: (Operation | Number)[]) =>
    ~firstOperationIndex(result);

  while (operationsRemaining(result)) {
    const operationIndex = firstOperationIndex(result);
    const operation = result[operationIndex] as Operation;

    const firstNumberIndex = operationIndex - 1;
    const firstNumber = result[firstNumberIndex] as Number;

    const secondNumberIndex = operationIndex + 1;
    const secondNumber = result[secondNumberIndex] as Number;

    result = result.reduce(
      (result: (Operation | Number)[], current: Operation | Number, index) => {
        return index === operationIndex
          ? [...result, combine(operation, firstNumber, secondNumber)]
          : [firstNumberIndex, secondNumberIndex].includes(index)
          ? result
          : [...result, current];
      },
      []
    );
  }

  return result;
};

export const calculate = pipe(
  parse,
  doOperations(["*", "/"]),
  doOperations(["+", "-"]),
  map(prop("value")),
  head
);