计算器

2021-01-06

面试题 16.26. 计算器

难度中等49收藏分享切换为英文接收动态反馈

给定一个包含正整数、加(+)、减(-)、乘(*)、除(/)的算数表达式(括号除外)，计算其结果。

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

示例 1:

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

示例 2:

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

示例 3:

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

说明：

你可以假设所给定的表达式都是有效的。
请不要使用内置的库函数 eval。

通过次数12,804

提交次数33,193

中缀表达式转后缀表达式_qianyayun19921028的博客-CSDN博客_中缀表达式转后缀表达式

首先假设我们需要转化的中缀表达式为：

a + b * c + ( d * e + f ) * g

第一种：基于堆栈的算法

从左到右扫描每一个字符。如果扫描到的字符是操作数（如a、b等），就直接输出这些操作数。

如果扫描到的字符是一个操作符，分三种情况：

（1）如果堆栈是空的，直接将操作符存储到堆栈中（push it）

（2）如果该操作符的优先级大于堆栈出口的操作符，就直接将操作符存储到堆栈中（push it）

（3）如果该操作符的优先级低于堆栈出口的操作符，就将堆栈出口的操作符导出（pop it）, 直到该操作符的优先级大于堆栈顶端的操作符。将扫描到的操作符导入到堆栈中（push）。

如果遇到的操作符是左括号”（”，就直接将该操作符输出到堆栈当中。该操作符只有在遇到右括号“)”的时候移除。这是一个特殊符号该特殊处理。

如果扫描到的操作符是右括号“）”，将堆栈中的操作符导出（pop）到output中输出，直到遇见左括号“（”。将堆栈中的左括号移出堆栈（pop ）。继续扫描下一个字符

如果输入的中缀表达式已经扫描完了，但是堆栈中仍然存在操作符的时候，我们应该讲堆栈中的操作符导出并输入到output 当中。

————————————————
版权声明：本文为CSDN博主「奋斗的小菜鸟！」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qianyayun19921028/article/details/89228263

双端队列

class Solution {
    public int calculate(String s) {
        if (s == null || s.length() == 0) return 0;
        String temp = s;
        temp = temp.replaceAll(" ", "");
        temp = temp.replace("+", "|");
        temp = temp.replace("-", "|");
        temp = temp.replace("*", "|");
        temp = temp.replace("/", "|");

        List<Character> opList = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '+' || c == '-' || c == '*' || c == '/') {
                opList.add(c);
            }
        }
        if (temp.length() == 0) return 0;

        String[] arr = temp.split("\\|");
        Deque<String> stack = new LinkedList<>();


        int index = 0;
        stack.offerLast(arr[0]);
        for (int i = 1; i < arr.length; i++) {
            if (opList.get(index) == '*' || opList.get(index) == '/') {
                int val1 = Integer.parseInt(stack.pollLast());
                int val2 = Integer.parseInt(arr[i]);
                int res = 0;
                if (opList.get(index) == '*') res = val1 * val2;
                else res = val1 / val2;
                stack.offerLast(Integer.toString(res));

            } else {
                stack.offerLast(opList.get(index) + "");
                stack.offerLast(arr[i]);
            }

            index++;
        }
        while (!stack.isEmpty() && stack.size() > 1) {
            int val1 = Integer.parseInt(stack.pollFirst());
            String op = stack.pollFirst();
            int val2 = Integer.parseInt(stack.pollFirst());
            int res = 0;
            if (op.equals("+")) res = val1 + val2;
            else res = val1 - val2;
            stack.push(Integer.toString(res));
        }

        return stack.isEmpty() ? 0 : Integer.parseInt(stack.pop());
    }
}

栈

class Solution {
    public int calculate(String s) {
        char[] cs = s.trim().toCharArray();
        Stack<Integer> st = new Stack();
        int ans = 0, i = 0;
        while(i < cs.length){
            if(cs[i] == ' ') {i++;continue;}
            char tmp = cs[i];
            if(tmp == '*' || tmp == '/' || tmp == '+' || tmp == '-'){
                i++;
                while(i < cs.length && cs[i] == ' ') i++;
            }
            int num = 0;
            while(i < cs.length && Character.isDigit(cs[i])){
                num = num * 10 + cs[i] - '0';
                i++;
            }
            switch(tmp){
                case '-':
                    num = -num;
                    break;
                case '*':
                    num = st.pop() * num;
                    break;
                case '/':
                    num = st.pop() / num;
                    break;
                default:
                    break;
            }
            st.push(num);
        }
        while(!st.isEmpty()) ans += st.pop();
        return ans;
    }

    
}

作者：luoweian
链接：https://leetcode-cn.com/problems/calculator-lcci/solution/java-si-lu-qing-xi-jian-ji-dai-ma-by-acw_weian/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。