Problem

Given an arithmetic string like 2+2*3 calculate result 8.

Assumptions you can make

  • string will be always well formed (no error checking needs to be done)
  • only operators passed in string will be + and *
  • only single digit numbers allowed

Example

input = 2*2*2+2*1*5
output = 18

input = 2+2*3
output = 8

Hers is scala code for the same

object Expression extends App {
  implicit class Converter(char: Char) {
    def toNum: Int = char - '0'
  }

  def evaluateExpression(s :List[Char]): Int = {
    s match {
      case left::op::List(right) =>  // a+b or a*b
        op match {
          case '+' =>  left.toNum + right.toNum
          case  _ =>   left.toNum * right.toNum
        }
      case left::op::right => // a+b*c or a*b+c
         op match {
           case '+' =>
             left.toNum + evaluateExpression(right)
           case '*' =>
             val nextAdd = right indexOf '+'
             val (multiplication ,pendingExpression) = if (nextAdd == -1) {
                                                         (right,List[Char]())
                                                       } else {
                                                         (right.take(nextAdd), right.drop(nextAdd + 1))
                                                       }
             val product = (multiplication.filter( _ != '*') map (_.toNum)).foldLeft(left.toNum) (_ * _)
             if (pendingExpression.isEmpty) product
             else product + evaluateExpression(pendingExpression)
          }
     }
   }
  List("3*3*3", "2+2*3", "0*0*1", "0+0*1", "0*0*1", "2+2*3*3", "2+2+2*3+2+2") foreach { expr =>
    println(expr + " = " + evaluateExpression(expr.toList))
  }
}

Output for above code

3*3*3 = 27
2+2*3 = 8
0*0*1 = 0
0+0*1 = 0
0*0*1 = 0
2+2*3*3 = 20
2+2+2*3+2+2 = 14
  • 1
    I rolled back your last edit. After getting an answer you are not allowed to change your code anymore. This is to ensure that answers do not get invalidated and have to hit a moving target. If you have changed your code you can either post it as an answer (if it would constitute a code review) or ask a new question with your changed code (linking back to this one as reference). Refer to this post for more information – Sᴀᴍ Onᴇᴌᴀ Dec 6 at 18:34

You might want to spend some time becoming more familiar with the Standard Library. You're doing a few things that are already provided for.

implicit class Converter(char: Char) {
  def toNum: Int = char - '0'
}

To convert a digit character into the value it represents: char.asDigit. If you have one or more digit characters in a string: digits.toInt

Your solution also fails for expressions like "2*2+3". It looks like the evaluateExpression() code doesn't anticipate that, in the recursive call evaluateExpression(pendingExpression), the value of pendingExpression might be a single digit.

But mostly, with the input under so many tight restrictions, you should consider what shortcuts might be available to you.

def evaluateExpression(s :String) :Int =
  s.split("\\+")
   .map(_.split("\\*")
         .map(_.toInt)
         .product)
   .sum
  • Thanks for pointing out the bug & alternative, I will update the code. As this exercise is more for interview preparation (as tagged), I didnt went for solution with split because i thought it will be more expensive (due to multiple iterations). But it seems I am wrong. For a string like this "3*3+3+3*3*3+2+2*3*0*0*1*0+0*1+0*0*1+2+2*3*2+2+2*3+2+2", Your solution is faster. Is it because of recursion in my solution? – vikrant Dec 6 at 17:57

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.