LetCode Basic Calculator(스택으로 표현식 값 계산)

3418 단어 #
제목: +,-,(,)만 포함하는 계산 표현식을 제시하고 계산 결과를 구합니다.
사고방식: 창고로 실현
코드는 다음과 같습니다.
public class Solution
{
    private int cal(int num1, int num2, char op)
    {
        switch(op) {
            case '+':
                return num1 + num2;
            case '-':
                return num1 - num2;
            default:
                return 0;
        }
    }

    public int calculate(String s)
    {
        String str = s.trim();
        Stack stackInt = new Stack();
        Stack stackChar = new Stack();

        Map map = new HashMap();
        map.put('(', 0); map.put('+', 1); map.put('-', 1); map.put(')', 2);

        for (int i = 0; i < str.length(); i++)
        {
            if (Character.isSpaceChar(str.charAt(i))) {
                continue;
            }

            //   ,       
            if (Character.isDigit(str.charAt(i))) {
                int sum = 0;
                int j = i;
                for (; j < str.length(); j++)
                {
                    if (Character.isDigit(str.charAt(j))) {
                        sum = sum * 10 + (char)(str.charAt(j) - '0');
                    } else {
                        break;
                    }
                }
                i = j - 1;
                stackInt.add(sum);
            } else {
                //    ,     ,    
                if (stackChar.isEmpty()) {
                    stackChar.add(str.charAt(i));
                    continue;
                }

                // ),        ,    (
                if (str.charAt(i) == ')') {
                    while (!stackChar.isEmpty() && stackChar.peek() != '(') {
                        int num2 = stackInt.pop();
                        int num1 = stackInt.pop();
                        char op = stackChar.pop();
                        int num = cal(num1, num2, op);
                        stackInt.push(num);
                    }

                    if (stackChar.peek() == '(') stackChar.pop();
                } else {
                    //                    ,    
                    if (str.charAt(i) != '(' && map.get(str.charAt(i)) > map.get(stackChar.peek())) {
                        stackChar.add(str.charAt(i));
                    } else {
                        //    ,                    
                        while (!stackChar.isEmpty() && str.charAt(i) != '(' && map.get(str.charAt(i)) <= map.get(stackChar.peek())) {
                            int num2 = stackInt.pop();
                            int num1 = stackInt.pop();
                            char op = stackChar.pop();
                            int num = cal(num1, num2, op);
                            stackInt.push(num);
                        }

                        stackChar.add(str.charAt(i));
                    }
                }

            }
        }

        while (!stackChar.isEmpty()) {
            int num2 = stackInt.pop();
            int num1 = stackInt.pop();
            char op = stackChar.pop();
            int num = cal(num1, num2, op);
            stackInt.push(num);
        }

        return stackInt.pop();

    }
}

좋은 웹페이지 즐겨찾기