Java solution using two stacks


  • 0
    S

    Similar to my previous solution for Basic Calculator II: https://discuss.leetcode.com/topic/51154/simple-java-solution

    Ideas:

    1. Filter the string first, get rid of spaces, and group multi-digit numbers into one string
    2. push every string into stack1, until we encounter ")", then we pop everything from stack1 onto stack2 until we encounter the first "(" from stack1, then we pop everything from stack2 to do the calculation, when the calculation is done, we push the intermediate result back to stack1, continue the loop until the end of the string array.
    3. when exiting, there are two possible cases:
      1. there's only one element in stack1, then we could simply pop it as return value;
      2. there could be a simple expression (without any open or close parentheses there any more), in this case, we just do the calculation again and return that value.
    public int calculate(String s) {
    	if (s == null || s.isEmpty())
    		return 0;
    
    	s = s.replaceAll("\\s", "");
    	char[] chars = s.toCharArray();
    	List<String> filteredStr = new ArrayList<String>();
    	for(int i = 0; i < chars.length;){
    		StringBuilder sb = new StringBuilder();
    		while (i < chars.length && Character.isDigit(chars[i])) {
    			sb.append(chars[i]);
    			i++;
    		}
    		if (i == chars.length) {
    			if (sb.toString().length() != 0) {
    				filteredStr.add(sb.toString());
    			}
    		} else {
    			if (sb.toString().length() != 0) {
    				filteredStr.add(sb.toString());
    			}
    			if(chars[i] == '+' || chars[i] == '-' || chars[i] == '(' || chars[i] == ')'){
    				filteredStr.add(String.valueOf(chars[i]));
    			}
    			i++;
    		}
    	}
    	
    	Stack<String> stack1 = new Stack();
    	Stack<String> stack2 = new Stack();
    	for(int i = 0; i < filteredStr.size();){
    		while(i < filteredStr.size() && !filteredStr.get(i).equals(")")){
    			stack1.push(filteredStr.get(i));
    			i++;
    		}
    		if(i != filteredStr.size()){
    			while(!stack1.isEmpty() && !stack1.peek().equals("(")){
    				stack2.push(stack1.pop());
    			}
    			stack1.pop();//this is to pop "(" since we use peek in the above while condition
    			int exp = 0;
    			while(!stack2.isEmpty()){
    				if(stack2.size() == 1){
    					stack1.push(stack2.pop());
    					break;
    				}
    				int operand1 = Integer.parseInt(stack2.pop());
    				String operator = stack2.pop();
    				int operand2 = Integer.parseInt(stack2.pop());
    				if(operator.equals("+")) exp = operand1 + operand2;
    				else if(operator.equals("-")) exp = operand1 - operand2;
    				stack2.push(String.valueOf(exp));
    			}
    			i++;
    		}
    	}
    	
    	if(stack1.size() == 1) return Integer.parseInt(stack1.pop());
    	
    	while(!stack1.isEmpty()){
    		stack2.push(stack1.pop());
    	}
    	while(!stack2.isEmpty()){
    		if(stack2.size() == 1){
    			stack1.push(stack2.pop());
    			break;
    		}
    		int exp = 0;
    		int operand1 = Integer.parseInt(stack2.pop());
    		String operator = stack2.pop();
    		int operand2 = Integer.parseInt(stack2.pop());
    		if(operator.equals("+")) exp = operand1 + operand2;
    		else if(operator.equals("-")) exp = operand1 - operand2;
    		stack2.push(String.valueOf(exp));
    	}
    	return Integer.parseInt(stack1.pop());
    }

Log in to reply
 

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