Parsing expression with exponents and evaluating

Question

I'm programming a basic command line calculator in java that can parse expressions and evaluate them, does not handle brackets yet.

For example an expression: \$9+9/2^2*5-1\$.

At this point I can give my program an expression that contains exponents, and It will evaluate them one by one until there are none left.

For example, I can input the following string: \$2^2+1\$ and it will output \$4.0+1\$.

public class Main {

    public static void main(String[] args) {
        String powerExpression = "2^2+1";

        loopPower(powerExpression);
    }

    public static void loopPower(String exp) {
        while (containsExponents(exp)) {
            exp = procPower(exp);
        }

        System.out.println("FINAL ANSWER IS: " + exp);

}
    public static boolean containsExponents(String exp) {
        boolean contains = false;
        for (int i = 0; i < exp.length(); i++) {
            if (exp.charAt(i) == '^') {
                contains = true;
                break;
            }
        }
        return contains;
    }

    public static String procPower(String exp) {
        int operandOneStart = 0;
        int operandTwoStart = 0;
        int operandTwoEnd = 0;
        boolean onFirst = true;
        boolean foundOp = false;

        for (int i = 0; i < exp.length(); i++) {
            if (isCharNumerical(exp.charAt(i))) {
                if (onFirst) {
                    operandOneStart = i;
                    onFirst = false;
                }
                if (foundOp) {
                    operandTwoStart = i;
                    //Perform op

                    String operandOne = "";
                    String operandTwo = "";
                    //Get operand1
                    for (int op1 = operandOneStart; op1 < exp.length();op1++) {
                        if (isCharNumerical(exp.charAt(op1))) {
                            operandOne += exp.charAt(op1);
                        }
                        else {
                            break;
                        }
                    }
                    //Get operand2
                    for (int op2 = operandTwoStart; op2 < exp.length(); op2++) {
                        if (isCharNumerical(exp.charAt(op2))) {
                            operandTwo += exp.charAt(op2);
                        }
                        else {
                            operandTwoEnd = (op2-1);
                            System.out.println("Op 2 End: " + operandTwoEnd);
                            break;
                        }

                        if (isCharNumerical(exp.charAt(op2)) & op2 == (exp.length()-1)) {
                            operandTwoEnd = op2;
                            System.out.println("Op 2 End: " + operandTwoEnd);
                        }
                    }

                    System.out.println("Operand One: " + operandOne);
                    System.out.println("Operand Two: " + operandTwo);

                    boolean noBeforenoAfter = false;
                    boolean yesBeforeyesAfter = false;
                    boolean noBeforeyesAfter = false;
                    boolean yesBeforenoAfter = false;

                    float opx1 = Float.valueOf(operandOne);
                    float opx2 = Float.valueOf(operandTwo);

                    if (operandOneStart == 0 & operandTwoEnd == (exp.length()-1)) {
                        noBeforenoAfter = true;
                        exp = String.valueOf(Math.pow(opx1, opx2));
                    }

                    if (operandOneStart > 0 & operandTwoEnd < (exp.length()-1)) {
                        yesBeforeyesAfter = true;
                        String before = "";
                        for (int a = 0;a < operandOneStart;a++) {
                            before += exp.charAt(a);
                        }
                        String after = "";
                        for (int a = operandTwoEnd+1; a < exp.length(); a++) {
                            after += exp.charAt(a);
                        }

                        double subans = Math.pow(opx1,opx2);
                        exp = before + String.valueOf(subans) + after;
                    }

                    if (operandOneStart == 0 & operandTwoEnd < (exp.length()-1)) {
                        noBeforeyesAfter = true;
                        String after = "";
                        for (int a = operandTwoEnd+1; a < exp.length(); a++) {
                            after += exp.charAt(a);
                        }
                        double subans = Math.pow(opx1,opx2);
                        exp = String.valueOf(subans) + after;

                    }

                    if (operandOneStart> 0 & operandTwoEnd == (exp.length()-1)) {
                        yesBeforenoAfter = true;
                        String before = "";
                        for (int a = 0;a < operandOneStart;a++) {
                            before += exp.charAt(a);
                        }
                        double subans = Math.pow(opx1,opx2);
                        exp = before+subans;
                    }

                    //
                    break;
                }
            }
            else {
                if (exp.charAt(i) == '^') {
                    foundOp = true;
                }
                else {
                    onFirst = true;
                    foundOp = false;
                }
            }
        }

        return exp;
    }

    public static boolean isCharNumerical(char c) {
        boolean numerical = false;

        switch (c) {
            case '0':
                numerical = true;
                break;
            case '1':
                numerical = true;
                break;
            case '2':
                numerical = true;
                break;
            case '3':
                numerical = true;
                break;
            case '4':
                numerical = true;
                break;
            case '5':
                numerical = true;
                break;
            case '6':
                numerical = true;
                break;
            case '7':
                numerical = true;
                break;
            case '8':
                numerical = true;
                break;
            case '9':
                numerical = true;
                break;
            case '.':
                numerical = true;
                break;
            default:
                numerical = false;
                break;
        }

        return numerical;
    }
}

What is the quality of what I have written/coded? Anything I need to change? Should I go on to make my parser be able to do other arithmetic operations such as multiplication, division, adding, subtracting, or does this need lots of improvement at this stage?

Answer 1

In a comment you state that you "was trying to follow PEMDAS", that is Parenthesis, Exponents, Multiply and Divide, Addition and Subtraction, which sounds like a good track to follow. However you would benefit from preprocessing your string into an array or list consisting of two types of elements, and that is numbers and tokens (like (, ), ^, *, /, +, -).

When this array is created you have a much easier task of walking through the array (or list) and simplify it step by step, going through the PEMDAS. With a proper list, you find your wanted operator, and then pick the number in front and after the operator and calculate it. Replace the three elements you justed calculated, and repeat simplification...

By the way, what I've just described is a simple variant of building an Abstract Syntax Tree (consisting of numbers and tokens), which you then parse into the expression you want to calculate. The great advantage of doing this in these two steps is that you can focus your attention on either picking numbers or tokens, or afterwards actually simplifying/calculating according to PEMDAS.

Sorry, for not providing actual code, but you seem to know enough to understand how to walk through the list once to extend the numbers and tokens. Afterwards, keep manipulating the array (or list), which hopefully also is known operations.

Added: I've asked a question my self here on Code Review, which implements a calculator like the one I've described above (with exception of parentheses) written in Python. Hopefully this could still give you some hints on another approach for making a calculator.

Addendum: Comments on code logic

In the following I'm going to ignore the restructure I've suggested, but try to give some comments on your existing code. This is to help you understand why you've been given comments that your code is a mess, having bad logic, and so on.

• Choose better and more meaningful names – The exp could be short of both expression and exponentiation, which is rather confusing when you only do exponentiation in your code. You also intermix exponents and power in containsExponents and loopPower, which is slightly confusing. I would rather use the full expression or possibly text, and containsPowerOperator and calculatePowers for these methods.

  Another example are the yesBeforenoAfter & co variables. These are both confusing and unused, and I'll come back to these later on.

  Lastly the operandOneStart and operandTwoEnd, I think I would rather use firstOperandStartIdx and secondOperandEndIdx which would clearer convey what they are used for.

• Extract more into functions - You could easily separate the entire loop for getting operands into a new function. You could call it like double firstOperand = new Operand(expression, firstOperandStartIdx), and if bold you let the firstOperand be a dedicated class having optional original text, value, and startIdx and endIdx parts.

• Simplify the rebuild of the expression – Instead of all of the code you've given with the yesBeforenoAfter & co, you could make this into a function as well, which simply concatenates the following string parts:

  • The substring from start of string to firstOperand.startIdx, or nothing if that is 0
  • The string version of the current result
  • The substring from secondOperand.endIdx to end of string, or nothing if that is 0

• Flag variables and first operand... – There are some logic related to keeping track of the start of the first operand and whether you've found the operator or not which I'm not entirely sure how it actually works. (And as previously suggested, this would be way simpler if you'd already processed the list into tokens like numbers and operators. :-).

  However I think you might have a bug here, and should test with expressions like 10^3 + 11^2 and see whether they give the expected output or not. I think I would have replaced the onFirst with setting the firstOperandStartIdx = -1 and testing against that. I would most likely also invert the if-statements so that it's clearer at the top what is happening, see refactored code below.

• Feature/bug: Your code will break on two exponential expression in the same expression – If I'm not mistaken your code will only accept one exponential expression, as you do a break after finding the operator. In my refactored code below, this is not handled either. But you should look into it

• Why do the containsExponents at all? – The code as it stands runs through the entire expression twice if it has the exponent operator. However you could simplify this by simply calling the loopPower (or calculatePowers:-) ) method once. The method would then loop the string once, and if nothing is found, it return the original expression. If the operator is found it still has only looped it once, but now it has rebuilt the expression without the exponential part, and are ready for next step.

• Simplify the isCharNumerical() – As suggested by πάντα ῥεῖ, you could simplify this function quite a bit...

Refactored code

I'll provide you with some untested code if you choose to proceed with your implementation and not going the route via tokens. This would need for a new class, Operand, something like the following:

public class Operand {
    String text;
    double value;
    int startIdx;
    int endIdx;

    public Operand(String text, int startIdx) {
        this.startIdx = startIdx;

        this.text = "";
        for (int idx = startIdx; idx < text.length(); idx++) {
            char currentChar = text.charAt(id);

            if (isCharNumerical(currentChar)) {
                this.text += currentChar;

            } else {
                this.endIx = idx - 1;
                break;
            }
        }
        this.value = Double.valueOf(this.text);
    }
}

And then your calculatePowers would look something like the following untested code:

public static String calculatePowers(String text) {
    int firstOperandStartIdx = -1;
    boolean foundOperator = false;
    int startNextPart = 0;

    for (int i = 0; i < text.length(); i++) {
        char currentCharacter = text.charAt(i);

        if (!isCharNumerical(currentCharacter)) {
           
            foundOperator = (currentCharacter == '^');
            
            // If this was not the operator we're looking for
            // flag that we need to start looking for a new operand
            if (!foundOperator) {
                firstOperandStartIdx = -1;
            }

        } else {
            // If start of operand hasn't been found, set this 
            // index to be start of number
            if (firstOperandStartIdx < 0) {
                firstOperandStartIdx = i;
            } 

            if (foundOperator) {
                Operand firstOperand = new Operand(text, firstOperandStartIdx);
                Operand secondOperand = new Operand(text, i);
                
                String new_expression = text.substring(startNextPart, firstOperand.startIdx);

                new_expression += String.valueOf(Math.pow(firstOperand.value, secondOperand.value);

                new_expression += text.substring(secondOperand.endIdx + 1, text.length());
      
                // This will need a little tweaking, if you want
                // the newly calculated part to be part of the next
                // expression as well... This is merely a start
                // related to fixing the only one exponential expression bug...
                startNextPart = secondOperand.endIdx;
            }
        }
    }

    return new_expression;
}

Answer 2

Just for one thing: The isCharNumerical() function doesn't actually need a switch statement, it could be simplified just as

public static boolean isCharNumerical(char c) {   
    return (c >= '0' && c <= '9');
}

Don't overcomplicate boolean conditions, just take them straightforward.

---

In general for your parser, make operator precedence clear at any state of parsing.

What you have in your example clearly states that operator ^ precedes operator +, which is the natural expectation. Require brackets to group math expressions being processed in different order.

Answer 3

• Don't assign to parameters. See multiple assignments to exp

• Use meaningful names. See loopPower and procPower

• separate logic and IO. See multiple System.out.println peppered in.

• Remove dead code. See noBeforenoAfter, yesBeforeyesAfter, noBeforeyesAfter, yesBeforenoAfter. I wonder what were you thinking.

• Remove duplication. e.g. Numerous occurrences of double subans = Math.pow(opx1,opx2); and for (...) { operand... += exp.charAt(...);}

• Don't mix precisions. e.g. double subans = Math.pow(opx1,opx2);. Use double and stick with it.

• Avoid long methods.

• Avoid multiple levels of nesting.