计算器

[编程题]计算器

热度指数：216 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

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

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

示例 :

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

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

示例1

输入

" 3/2 "

输出

备注:

语言不限

算法知识视频讲解

Java

牛客71026566号

  public long calculate (String s) {
        // write code here
        List<String> compute = patternIndex(s);

        Queue<String> queue = new ArrayDeque<>();
        // 四为和俩位的时候单独拿
        Set<Integer> computeIndex = new TreeSet<>();
        for (int i = 1; i < compute.size(); i+=2) {
             if (compute.get(i).equals("*")||compute.get(i).equals("/")){
                 computeIndex.add(i);
                 computeIndex.add(i-1);
                 computeIndex.add(i+1);
             }
        }
        List<Integer> list = new ArrayList<>(computeIndex);
        for (int i = 0; i <list.size(); i++) {
            System.out.println(compute.get(list.get(i)));
            queue.add(compute.get(list.get(i)));
        }
        for (int i = list.size()-1; i >=0; i--) {

           compute.remove((int)list.get(i));
        }
        for (int i = 1; i < compute.size(); i+=2) {
                if ("+".equals(compute.get(i))||"+".equals(compute.get(i))){
                    queue.add(compute.get(i));
                    queue.add(compute.get(i-1));
                }else {
                    queue.add(compute.get(i-1));
                    queue.add(compute.get(i));
                }
        }
        long l = Long.valueOf(queue.poll());
        int size = queue.size();
        for (int i = 1; i < size; i+=2) {
            String poll1 = queue.poll();
            l = compute(l, Long.valueOf(queue.poll()), poll1);
        }
        return l;
    }

     private Long compute(Long pre,Long next,String compote){
         switch (compote){
             case "+": return pre+next;
             case "-": return pre-next;
             case "*": return pre*next;
             case "/": return pre/next;
             default:{
                 return 0L;
             }
         }

     }

    private List<String> patternIndex(String s){
        char[] chars = s.toCharArray();
        List<String> list = new ArrayList<>();
        String num = "";
        for (int i = 0; i < chars.length; i++) {
           String str = chars[i]+ "";
            if (!str.matches("[0-9]")){
                if (!str.equals(" ")) {
                    list.add(num);
                    list.add(str);
                    num = "";
                }
            }else {
                num += chars[i];
            }
        }
        if (!num.equals("")) {
            list.add(num);
        }
        return list;
    }

各位大佬，请问我这样写有bug吗？

发表于 2023-05-22 23:19:58 回复(0)

菲尼克斯弗兰克

提供一个思路，每次遇到符号处理前一个符号的运算，简洁明了

import java.util.*;

public class Solution {
    public long calculate (String s) {
        long n = 0;
        char op = '+';
        ArrayDeque<Long> stack = new ArrayDeque<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c >= '0') { // 当前是数字
                n = n * 10 + c - '0';
            }
            if ((c < '0' && c != ' ') || i == s.length()-1) { // 是符号或者达到结尾
                if (op == '+') {
                    stack.push(n);
                } else if (op == '-') {
                    stack.push(-n);
                } else if (op == '*') {
                    stack.push(stack.pop() * n);
                } else if (op == '/') {
                    stack.push(stack.pop() / n);
                }
                n = 0;
                op = c;
            }
        }
        long res = 0;
        while (!stack.isEmpty()) {
            res += stack.pop();
        }
        return res;
    }
}

发表于 2022-06-08 12:47:25 回复(0)

ndjndjdhjd

没怎么优化的Java版本，先压入所有的操作数和运算符，遇到运算符为加减时需要进行特判，因为存在优先级问题。

import java.util.*;
 
 
public class Solution {
    Stack<Long> num = new Stack<>();
    Stack<Character> ch = new Stack<>();
 
    public long calculate(String s) {
        char[] c = s.toCharArray();
        int cLen = c.length;
        for (int i = 0; i < cLen; i++) {
            if (Character.isDigit(c[i])) {
                int j = i + 1;
                while (j < cLen && Character.isDigit(c[j])) {
                    ++j;
                }
                num.push(parse(s,i, j));
                i = j - 1;
            } else if (isChar(c, i)) {
                ch.push(c[i]);
            }
        }
        return cal();
    }
 
    private long parse(String s,int start, int end) {
        return Long.parseLong(s.substring(start,end));
    }
 
    private boolean isChar(char[] c, int i) {
        return c[i] == '-' || c[i] == '+' || c[i] == '*' || c[i] == '/';
    }
 
    private long cal() {
        while (!ch.isEmpty()) {
            char c = ch.pop();
            long a = num.pop();
            long b = num.pop();
            if (c == '*') {
                num.push(b * a);
            } else if (c == '/') {
                num.push(b / a);
            } else if (c == '+') {
                if(!ch.isEmpty() && (ch.peek() == '*' || ch.peek() == '/')){
                    long c3 = num.pop();
                    char cc = ch.pop();
                    if(cc == '*'){
                        num.push(c3 * b);
                    }else{
                        num.push(c3 / b);
                    }
                    num.push(a);
                    ch.push(c);
                }else{
                    num.push(b + a);
                }
            } else if (c == '-') {
                if(!ch.isEmpty() && (ch.peek() == '*' || ch.peek() == '/')){
                    long c3 = num.pop();
                    char cc = ch.pop();
                    if(cc == '*'){
                        num.push(c3 * b);
                    }else{
                        num.push(c3 / b);
                    }
                    num.push(a);
                    ch.push(c);
                }else{
                    num.push(b - a);
                }
            }
        }
        return num.pop();
    }
}

发表于 2021-03-28 22:04:52 回复(0)