Simple Java Solution


  • 1
    S

    Straightforward and easy to understand:

    1. Get rid of ” ” from the input string and group multi-digit numbers into one string and store the result into an array of Strings because I’ll have to access str[i+1] later in the code, so if it’s multi-digit number, I’ll only get its left-most digit which is wrong.
    2. Do division and multiplication in the first round since they have higher precedence.
    3. Reverse the stack to get the left-to-right order since the order for addition and subtraction matters.
    4. then in the new stack, do addition and subtraction.
    public int calculate(String s) {
    	if (s == null || s.isEmpty())
    		return 0;
    
    	Stack<String> stack = new Stack();
    	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++;
    		}
    	}
    	
    	for(int i = 0; i < filteredStr.size(); i++){
    		if(!filteredStr.get(i).equals("*") &&
    				!filteredStr.get(i).equals("/")) {
    			stack.push(filteredStr.get(i));
    		}
    		else {
    			if(!stack.isEmpty()){
    				int exp = 0;
    				int operand = Integer.parseInt(stack.pop());
    				if(filteredStr.get(i).equals("*")){
    					exp = operand * Integer.parseInt(filteredStr.get(i+1));
    				} else if(filteredStr.get(i).equals("/")){
    					exp = operand / Integer.parseInt(filteredStr.get(i+1));
    				}
    				stack.push(String.valueOf(exp));
    				i++;
    			}
    		}
    	}
    	
    	//move everything from this stack into a new stack to get everything from left to right since cases like this: String s = "1-1+1" cannot be calculated from right to left, which means 1-(1+1) = -1, but the correct answer is actually 1, so we'll have to reverse the stack
    	Stack<String> newStack = new Stack();
    	while(!stack.isEmpty()){
    		newStack.push(stack.pop());
    	}
    	
    	while (!newStack.isEmpty()) {
    		if (newStack.size() == 1)
    			return Integer.parseInt((newStack.pop()));
    		int operand1 = Integer.parseInt(newStack.pop());
    		String operator = newStack.pop();
    		int operand2 = Integer.parseInt(newStack.pop());
    		long exp = 0;
    		if (operator.equals("+")) {
    			exp = operand2 + operand1;
    		} else if (operator.equals("-")) {
    			exp = operand1 - operand2;
    		}
    		newStack.push(String.valueOf(exp));
    	}
    	
    	return Integer.parseInt((newStack.pop()));
    }

Log in to reply
 

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