LetCode: 227. 简单计算器2

忘是亡心i 2022-05-04 13:28 126阅读 0赞

# 提示 #

LintCode中的相关算法题实现代码，可以在我的[GithHub][]中下载。

# 题目需求 #

实现一个基本的计算器来计算一个简单的字符串表达式的值。

字符串表达式仅包含非负整数，`+`， `-` ，`*`，`/` 四种运算符和空格 ` `。 整数除法仅保留整数部分。

**示例 1:**

输入: "3+2*2"
    输出: 7

**示例 2:**

输入: " 3/2 "
    输出: 1

**示例 3:**

输入: " 3+5 / 2 "
    输出: 5

# 解题思路 #

使用栈数据结构，当读到一个操作数的时候，立刻将它放入operatorSum Stack中。

如果见到任何其他的符号“+”、“-" 后，将Operator Stack中所有的元素弹出，并且弹出operatorSum Stack 中两个操作数。然后计算，将计算的结果放入operatorSum Stack。

如果见到任何其他的符号“\*”、“/" 后, 弹出Operator Stack中元素，直到遇到“+”、“-" 或者栈中元素为空。

# 实现代码 #

public class _227_Calculate {
        public int calculate(String s) {
            Stack<Character> stack=new Stack<>();
            Stack<Integer> opeartorNums=new Stack<>();
            for(int i=0; i< s.length();i++){
                char ch= s.charAt(i);
                switch (ch) {
                    case '+':
                        while (!stack.isEmpty()){
                            calucateHelper(stack, opeartorNums);
                        }
                        stack.push(ch);
                        break;
                    case '-':
                        while (!stack.isEmpty()){
                            calucateHelper(stack, opeartorNums);
                        }
                        stack.push(ch);
                        break;
                    case '*':
                        while (!stack.isEmpty() && stack.peek() =='*' || stack.peek() == '/'){
                            calucateHelper(stack, opeartorNums);
                        }
                        stack.push(ch);
                        break;
                    case '/':
                        while (!stack.isEmpty() && stack.peek() == '*' || stack.peek() == '/'){
                            calucateHelper(stack, opeartorNums);
                        }
                        stack.push(ch);
                        break;
                    case ' ':
                        break;
                    default:
                        int start=i;
                        while (i<s.length() && Character.isDigit(s.charAt(i))){
                            i++;
                        }
                        opeartorNums.push(Integer.valueOf(s.substring(start,i)));
                        --i;
                        break;
                }
            }
            while (!stack.isEmpty()){
                calucateHelper(stack, opeartorNums);
            }
            return opeartorNums.pop();
        }
    
        private void calucateHelper(Stack<Character> stack, Stack<Integer> opeartorNums) {
            Character character = stack.pop();
            int result = operatorNums(opeartorNums.pop(), opeartorNums.pop(), character);
            opeartorNums.push(result);
        }
    
        public int operatorNums(int num1, int num2, Character operator){
            switch (operator){
                case '+':
                    return num1+num2;
                case '-':
                    return num2-num1;
                case '*':
                    return num1*num2;
                case '/':
                    return num2/num1;
                default:
                    return -1;
            }
        }
    
        public static void main(String[] args) {
            _227_Calculate calculate=new _227_Calculate();
            int calculate1 = calculate.calculate("3+2*2-6/5");
            System.out.println(calculate1);
        }
    }

[GithHub]: https://github.com/Tjcug/LeetCode