Java OOO solution


  • 0
    T
    1. Divide the equation into left hand side (LHS) and right hand side (RHS)
    2. build tree for each side.
    3. Evaluate the tree on each side.
    4. Final stage is to resolve both the sides and capture edge cases.
    
        public String solveEquation(String equation) {
            if (null == equation){
                return null;
            }
            String[] split = equation.split("=");
            String left = split[0];
            String right = split[1];
    
            StringNode leftTree = buildTree(left);
            StringNode rightTree = buildTree(right);
    
            EqResult leftResult = traversal(leftTree);
            EqResult rightResult = traversal(rightTree);
    
            String result = evalResults(leftResult, rightResult);
            return result;
        }
    
        private String evalResults(EqResult left, EqResult right){
    
            int xTimes = left.xTimes - right.xTimes;
            int val = right.val - left.val;
    
            if (xTimes == 0){
                // bad situation
                if (val == 0){
                    return "Infinite solutions";
                }else{
                    return  "No solution";
                }
            }
    
            if (xTimes != 1){
                val = val/xTimes;
                xTimes = 1;
            }
    
            StringBuilder sb = new StringBuilder();
            if (xTimes >1) {
                sb.append(xTimes);
            }
    
            sb.append("x=");
            sb.append(val);
    
            return sb.toString();
        }
    
    
        private StringNode buildTree(String eq){
            char[] chars = eq.toCharArray();
            StringNode root = null;
            String s = "";
    
            for (Character c : chars){
    
                if (c == '+' || c == '-'){
    
                    StringNode op = new StringNode(c.toString());
                    StringNode sn = new StringNode(s);
                    s = "";
                    if (null == root){
                        root = op;
                        root.left = sn;
                    }else {
                        root.right = sn;
                        op.left = root;
                        root = op;
                    }
                }else {
                    s += c;
                }
            }
    
            if (!s.isEmpty()){
                StringNode sn = new StringNode(s);
                if (null != root) {
                    root.right = sn;
                }else {
                    root = sn;
                }
            }
    
            return root;
        }
    
        private EqResult traversal(StringNode stringNode){
            if (null == stringNode){
                return new EqResult(0, 0);
            }
    
            if (null == stringNode.left && null == stringNode.right){
                return  extractResult(stringNode.val);
            }
    
            EqResult left = traversal(stringNode.left);
            EqResult right = traversal(stringNode.right);
    
            int xTimes = 0;
            int val = 0;
            if (stringNode.val.equals("-")){
                xTimes = left.xTimes - right.xTimes;
                val = left.val  - right.val;
            }else if (stringNode.val.equals("+")){
                xTimes = left.xTimes + right.xTimes;
                val = left.val  + right.val;
            }else {
                throw new IllegalArgumentException("Expected +/- but found "+ stringNode.val);
            }
    
            return new EqResult(xTimes, val);
        }
    
        private static class StringNode {
            String val;
            StringNode left;
            StringNode right;
    
            public StringNode(String v){
                val = v;
            }
    
    
        }
    
        private static class EqResult {
            int xTimes;
            int val;
            public EqResult(int x, int v){
                xTimes = x;
                val = v;
            }
    
            @Override
            public String toString() {
                return "EqResult{" +
                        "xTimes=" + xTimes +
                        ", val=" + val +
                        '}';
            }
        }
    
    
        private EqResult extractResult(String str){
            int sum = 0;
            boolean hasX = false;
            char[] chars = str.toCharArray();
            boolean hasZero = false;
            for (Character c : chars){
                if (c == 'x'){
                    // hasX
                    hasX = true;
                }else {
                    if (c == '0'){
                        hasZero = true;
                    }
                    sum = sum * 10 + Integer.parseInt(c.toString());
                }
            }
    
            EqResult eqResult = null;
            if (hasX){
                if (sum == 0){
                    if (!hasZero) {
                        eqResult = new EqResult(1, 0);
                    }else {
                        eqResult = new EqResult(0, 0);
                    }
                }else {
                    eqResult = new EqResult(sum, 0);
                }
            }else {
                eqResult = new EqResult(0, sum);
            }
    
            return eqResult;
        }
    
    

    Some optimizations I plan to do. This would be to evaluate the tree while building it


Log in to reply
 

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