My Java solution with recursion


  • 0
    Q

    I may have overengineered this a bit.

    public class Solution {
        public int calculate(String s){
    		Expression expr = new Expression();
    		this.generateExpressions(s, 0, expr);
    		return expr.evaluate();
    	}
    	public int generateExpressions(String s, int index, Expression expr){
    		int result = 0;
    		for (int i=index;i<s.length();i++){		
    			char c = s.charAt(i);
    			if (Character.isDigit(c)){
    				StringBuffer buff = new StringBuffer();
    				buff.append(c);
    				for (int j=i+1;j<s.length();j++){
    					c = s.charAt(j);
    					if (Character.isDigit(c)){
    						i++;
    						buff.append(s.charAt(i));
    					}
    					else{
    						break;
    					}
    				}
    				expr.add(Integer.parseInt(buff.toString()));
    			}
    			else if ( c =='('){
    				Expression exp = new Expression();
    				expr.add(exp);
    				i = generateExpressions(s, i+1, exp);
    			}
    			else if (c == ')'){
    				return i;
    			}
    			else if (c == '+' || c == '-'){
    				expr.add(s.charAt(i));
    			}
    		}
    		return result;
    	}
    	
    	private static class Expression{
    		Queue<Object> queue = new ArrayDeque<Object>();
    		public void add(Object obj){
    			queue.offer(obj);
    		}
    		public int evaluate(){
    			int result = 0;
    			Character sign = '+';
    			while (!queue.isEmpty()){
    				Object obj = queue.poll();
    				if (obj instanceof Expression){
    					if (sign == '+'){
    						result = result + ((Expression)obj).evaluate();
    					}
    					else{
    						result = result - ((Expression)obj).evaluate();
    					}
    				}
    				if (obj instanceof Character){
    					sign = ((Character)obj).charValue();
    				}
    				else if (obj instanceof Integer){
    					if (sign == '+'){
    						result = result + ((Integer)obj).intValue();
    					}
    					else{
    						result = result - ((Integer)obj).intValue();
    					}
    				}
    			}
    			return result;
    		}
    	}
    }

  • 0
    Q

    After some cleanup.

     public class Solution {
    	public int calculate(String s){
    		ComplexExpression expr = new ComplexExpression(1);
    		this.generateExpressions(s, 0, expr);
    		return expr.evaluate();
    	}
    	public int generateExpressions(String s, int index, ComplexExpression expr){
    		int sign = 1;
    		for (int i=index;i<s.length();i++){		
    			char c = s.charAt(i);
    			if (Character.isDigit(c)){
    			    StringBuffer buff = new StringBuffer(String.valueOf(c));
    				for (;i<s.length()-1 && Character.isDigit(s.charAt(i+1));){
    					buff.append(s.charAt(++i));
    				}
    				expr.add(new IntegerExpression(Integer.parseInt(buff.toString()), sign));
    				sign = 1;
    			}
    			else if ( c =='('){
    				ComplexExpression exp = new ComplexExpression(sign);
    				expr.add(exp);
    				i = generateExpressions(s, i+1, exp);
    				sign = 1;
    			}
    			else if (c == ')'){
    				return i;
    			}
    			else if (c == '-'){
    				sign = -1;
    			}
    		}
    		return 0;  //this return is not used.
    	}
    	
    	private interface Expression{
    	    public int evaluate();
    	}
    	private class ComplexExpression implements Expression{
    		private Queue<Expression> queue = new ArrayDeque<Expression>();
    		private int sign = 1;
    		public ComplexExpression(int sign){
    			this.sign = sign;
    		}
    		public void add(Expression obj){
    		    queue.offer(obj);
    		}
    		public int evaluate(){
    			int result = 0;
    			while (!queue.isEmpty()){
    				result += queue.poll().evaluate();
    			}
    			return sign*result;
    		}
    	}
    	private class IntegerExpression implements Expression{
    		private int value;
    		private int sign;
    		public IntegerExpression(int val, int sign){
    			this.sign = sign;
    			this.value = val;
    		}
    		public int evaluate(){
    			return sign*value;
    		}
    	}
    }

Log in to reply
 

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