Java 8, short and using simple regex tokenization, detailed explanation


  • 1

    There are many ways to separate out the tokens and once the tokens are separated the logic to evaluate them is simple.
    My approach to tokenize has 2 steps.

    • First split the string using "+"
    • Each of the tokens obtained above can be categorized into the following
      - A single positive token like 5x or 10, in which case we already have the token
      - A group of tokens separated by "-" like 5x-5-10, in which case we split this now based on "-" and handle all the tokens except the first one as negative.

    An example : 2x+3x-6x-5+8-2x- 9
    On splitting using "+" we get:

    • 2x : already a valid token
    • 3x : already a valid token
    • -6x-5 : split using "-" => "", 6x, 5 => we handle "" as positive and everything else as negative
    • 8-2x-9 : split using "-" => 8, -2x, -9 => we handle 8 as positive and everything else as negative

    General flow of the algorithm:

    solveEquation => splits the equation into two using "=" and solves them individually and combines the result.

    solve => given one side of the equation, separate out the tokens using the 2 phase split approach of "+" and "-" and process them

    process => given a single token, add it to the appropriate result array

    public static String solveEquation(String equation) {
            String[] parts = equation.split("=");
            final int[][] res = new int[2][2];
            IntStream.range(0, 2).forEach(i -> solve(parts[i], res[i]));
    
            float num = res[1][1] - res[0][1], denom = res[0][0] - res[1][0];
    
            if(num == 0 && denom == 0) return "Infinite solutions";
            if(denom == 0) return "No solution";
            String ret =  "x=" + num/denom;
            ret =  ret.endsWith(".0") ? ret.substring(0, ret.length() - 2) : ret;
            return ret.endsWith("-0") ? "x=0": ret;
        }
    
        private static void solve(String eqn, int[] res) {
            Arrays.stream(eqn.split("\\+")).forEach( x -> {
                String[] arr = x.split("-");
                if(!arr[0].isEmpty()) process(arr[0], res);
                IntStream.range(1, arr.length).forEach(i -> process("-"+arr[i], res));
    
            });
        }
    
        private static void process(String token, int[] res) {
            token = token.equals("x") ? "1x" : token.equals("-x") ? "-1x" : token;
            int i = token.endsWith("x") ? 0 : 1;
            res[i] += Integer.parseInt(token.substring(0, token.length() - (i ^ 1)));
        }
    

  • 0
    C

    Nice approach.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.