문제 풀이[Stack] - 괄호 문제, 계산기 문제, 브라우저 구현

괄호 문제

 

public static boolean isBalanced(String str){
    Stack<Character> stack = new Stack<>();

    for(int i=0;i<str.length();i++){
        char c = str.charAt(i);
        if(c=='('||c=='{'||c=='['){
            stack.push(c);
        }else if(c==')'||c=='}'||c==']'){
            if(stack.isEmpty()){
                return false;
            }
            char top = stack.pop();
            if(((c==')')&&top!='(') || ((c=='}')&&top!='{') || ((c==']')&&top!='[')){
                return false;
            }
        }
    }
    return stack.isEmpty();
}

 

 

계산기 구현(괄호 있는 계산기 구현 문제)

 

중위 수식을 후위 수식으로 바꾸면서 후위 수식을 계산하는 방법이었음.

 

public static double calculate(String str){
    Stack<Double> numbers = new Stack<>();
    Stack<Character> operators = new Stack<>();

    int len = str.length();
    for(int i=0;i<len;i++){
        char ch = str.charAt(i);
        if(Character.isDigit(ch)){
            double num = ch - '0';
            while(i+1<len && Character.isDigit(str.charAt(i+1))){
                num = num * 10 + (str.charAt(i + 1) - '0');
                i++;
            }
            numbers.push(num);
        } else if (ch == '(') {
            operators.push(ch);
        } else if (ch ==')'){
            while(operators.peek()!='('){
                double result = applyOperation(operators.pop(), numbers.pop(), numbers.pop());
                numbers.push(result);
            }
            operators.pop();
        }else if(ch == '+'|| ch == '-' || ch=='*' || ch=='/'){
            while(!operators.isEmpty() && hasPrecedence(ch, operators.peek())){
                double result = applyOperation(operators.pop(), numbers.pop(), numbers.pop());
                numbers.push(result);
            }
            operators.push(ch);
        }
        while(!operators.isEmpty()){
            double result = applyOperation(operators.pop(), numbers.pop(), numbers.pop());
            numbers.push(result);
        }
    }
    return numbers.pop();
}

public static double applyOperation(char operator, double b, double a){
    switch(operator){
        case '+':
            return a+b;
        case '-':
            return a-b;
        case '*':
            return a*b;
        case '/':
            if (b==0){
                throw new UnsupportedOperationException("Cannot divide by zero.");
            }
            return a / b;
    }
    return 0;
}

public static boolean hasPrecedence(char op1, char op2){
    if(op2 == '(' || op2 == ')'){
        return false;
    }
    if((op1 == '*' || op1 == '/') && (op2 == '+' || op2 =='-') ){
        return false;
    }
    return true;
}

 

 

브라우저 구현하기

 

브라우저 앞으로 가기, 뒤로 가기, 새로운 페이지 이동을 스택을 사용하여 구현해보는 문제

 

public static ArrayList<Stack> browserStack(String[] actions, String start){
    Stack<String> prev = new Stack<>();
    Stack<String> curr = new Stack<>();
    Stack<String> next = new Stack<>();

    ArrayList<Stack> result = new ArrayList<>();

    curr.push(start);

    for(int i=0;i<actions.length;i++){
        try{
            int b = Integer.parseInt(actions[i]);
            if(b==-1 && !prev.isEmpty()){
                next.push(curr.pop());
                curr.push(prev.pop());
            }else if(b==1 && !next.isEmpty()){
                prev.push(curr.pop());
                curr.push(next.pop());
            }
        }catch (NumberFormatException e){
            prev.push(curr.pop());
            curr.push(actions[i]);
            if(!next.isEmpty())
                next.clear();
        }
    }

    result.add(prev);
    result.add(curr);
    result.add(next);

    return result;
}