4
\$\begingroup\$

I saw that interview question online and gave it a try:
Implement a function that gets a string which represents an arithmethic expression: contains only numbers or the the operators: '+', '-', '*', '/'.
The function returns the calculation result of the arithmethic expression which appears in the string.
This need to be done in O(n) run-time (n is the length of the string) and O(1) extra space.

Example:

"1+2*3" -> 7               

I succeed in implementing this (based mainly on some code I found online), but I just have one problem: logic is too complicated. So when reviewing the code, please tell me how can I simplify the logic here.

Here is the code:

class ArithmethicalStatments {

  private static int applyOperator(char operand, int firstNum, int secondNum){
      switch (operand) {
        case '*':
            firstNum *= secondNum;
            break;
        case '/':
            firstNum /= secondNum;
            break;
        case '+':
            firstNum = secondNum;
            break;
        case '-':
            firstNum = -secondNum;
            break;
      }

      return firstNum;
  }

  public static int calc(String str){
    int sum = 0;
    int lastApplyOpRes = 0;
    int lastNum = 0;
    int len = str.length();
    char prevOperator = '+';

    for (int i = 0; i < len; i++) {
        char c = str.charAt(i);

        if (c >= '0' && c <= '9') {
            lastNum = lastNum * 10 + c - '0';
            continue;
        }

        lastApplyOpRes = applyOperator(prevOperator, lastApplyOpRes , lastNum);
        lastNum = 0;

        switch (c) {
            case '+':
            case '-':
                sum += lastApplyOpRes;
                lastApplyOpRes = 0;
                break;
        }

        prevOperator = c;
    }

    lastApplyOpRes = applyOperator(prevOperator, lastApplyOpRes , lastNum);

    return sum + lastApplyOpRes;
  }
}              

In case you want to modify the code- some Junit tests I wrote for your convenience:

import static org.junit.jupiter.api.Assertions.*;
import org.junit.jupiter.api.Test;

class ArithmethicalStatmentsTest {

    @Test
    void testEmpty() {
        assertEquals(0, ArithmethicalStatments.calc(""));
    }

    @Test
    void testOneNum() {
        assertEquals(5, ArithmethicalStatments.calc("5"));
    }

    @Test
    void testPlus() {
        assertEquals(8, ArithmethicalStatments.calc("5+3"));
    }

    @Test
    void testMul() {
        assertEquals(15, ArithmethicalStatments.calc("5*3"));
    }

    @Test
    void testMulPlus() {
        assertEquals(8, ArithmethicalStatments.calc("2*3+2"));
    }

    @Test
    void testPlusMul() {
        assertEquals(11, ArithmethicalStatments.calc("2+3*3"));
    }

    @Test
    void testPlusMulPlus() {
        assertEquals(16, ArithmethicalStatments.calc("2+3+3*3+2"));
    }

    @Test
    void testMinus() {
        assertEquals(2, ArithmethicalStatments.calc("5-3"));
    }

    @Test
    void testDivision() {
        assertEquals(2, ArithmethicalStatments.calc("6/3"));
    }

    @Test
    void testMinusPlus() {
        assertEquals(1, ArithmethicalStatments.calc("2-3+2"));
    }

    @Test
    void testPlusDivide() {
        assertEquals(5, ArithmethicalStatments.calc("3+4/2"));
    }

    @Test
    void testAll() {
        assertEquals(6, ArithmethicalStatments.calc("2-3+3/3+2*3"));
    }

}
\$\endgroup\$

2 Answers 2

1
\$\begingroup\$

If your logic is too complicated, why don't you try to separate the concerns. You may create a Parser that will contains more well-named method to parse handle the characters in your stream. This one can either produce an object that is evaluated to produce your result or it can call methods on another class to evaluate each expression as soon as they are found (like the DOM vs SAX parsers).

\$\endgroup\$
1
\$\begingroup\$

Your applyOperator consists solely of a switch statement. Rather than having them all assign to firstNum, then returning the value, you might as well directly return the result...

private static int applyOperator(char operand, int firstNum, int secondNum){
    switch (operand) {
        case '*':
            return firstNum * secondNum;
        case '/':
            return firstNum / secondNum;
        case '+':
            return secondNum;
        case '-':
            return -secondNum;
    }
    return firstNum;
}

This flags up some non-intuitive behaviour, both +- operators ignore the first number and only operate on the second number. This is because half of the behaviour sits in the calling method. The default behaviour for an unknown operator is also to simply return the first number. This might be acceptable for your because of the challenge parameters, however consider throwing an exception on an unknown operator...

Bug?

The following test fails:

assertEquals(6, ArithmethicalStatments.calc("-3*-2"));

Maybe the question sets restrictions on the values that can be used, however, assuming you're supposed to be able to use negative numbers, the way you're handling the '-' operator breaks this (the result for the above comes back as '-2').

The calculator basically consists of number tokens, separated by operators. So, you can get a number (which consists of any number of '-', followed by numerals), then a single character operator, then back to a number etc.

Each token could be separated by white space, again this doesn't work currently, adding spaces means that "5 + 3" resolves to 5, rather than 8....combined with the lack of errors reported this is confusing.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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