数据结构——基本计算器的实现-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构——基本计算器的实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、不带括号的计算器

1.整体思想：

2.具体细节：

（1）字符串中有空格

（2）表达式开头可能是符号

（3）将数字放在第一个栈中

（4）出现“*”和“/”

（5）出现“+”和“-”

（6）完成运算

3.完整代码：

二、带括号的计算器

完整代码：

代码简化：

计算器是我们生活中经常会用到的物品，现在我们需要利用栈和队列的知识，来自己编写一个程序，来实现计算器的基本功能。

一、不带括号的计算器

在运算中，我们需要遵循运算符号的优先级，先乘除，后加减，有括号的先运算括号里面的。由此可见，在加上括号后，难度会有点儿大，所以我们现在先完成不带括号的计算器，后面在实现带括号的计算器。

1.整体思想：

表达式以字符串形式给予的，所以我们需要在字符上进行操作。我们可以创建两个栈，一个用来存放数据元素，一个用来存放符号元素。在符号栈里面获取到符号后，将数据栈里面的两个元素出栈进行操作，然后再放回到数据栈里面。如此操作，最后便能得到这个表达式的运算结果。

2.具体细节：

在代码实现的过程中，会出现一些问题，接下来我会一一解答并附上解决的代码。

（1）字符串中有空格

可以在所有运算前，将字符串里的所有空格删除或替换。（replace（）方法来替换字符串里的空格）

 String s = "1+2 / 5";
s = s.replace(" ", "");
//s="1+2/5"

（2）表达式开头可能是符号

在字符串前加一个"0"（如果是"-"开头，在运算时，没有与之匹配的前一项数据元素，会有报错）

String s="-1+2";
s = '0' + s;
//s="0-1+2"

（3）将数字放在第一个栈中

数字可能会不止一位，所以我们需要判断数字的位数，然后再进行存放

   char c = s.charAt(i);//循环得到字符串的每一个字符
if (c >= '0' && c <= '9') {//判断字符是不是数字
   int x = 0;
   while (i < s.length() && s.charAt(i) >= '0' && s.charAt(i) <= '9') {
/*
循环遍历，如果下一个字符依旧是数字，就将前面的字符乘10作为上一位，加后面的字符
-"0"是为了将字符转为数字（减的是ASKII码值，例如"0"-"0"就是0的ASKII减去0的ASKII，得到的数也就是0）
*/
       x = x * 10 + s.charAt(i++) - '0';//得到多位数的数字
   }
   i--;//在判断是否为数字时得到的字符会多加一位，会出现跳过下一个字符的情况，所以要对索引进行减1的操作
   stack1.push(x);
 }

（4）出现“*”和“/”

乘除需要先进行运算，运算时需要获取后面的元素和刚刚入栈的元素。在获取后面的元素时也需要进行判断元素的位数，才能进行运算。

if (i > 0 && (c == '*' || c == '/')) {
   int num1 = stack1.pop();
   int num2 = 0;
   while (i + 1 < s.length() && (s.charAt(i + 1) == ' ')) {
      i++;
   }
   int temp = 0;
   while (i + 1 < s.length() && s.charAt(i + 1) >= '0' && s.charAt(i + 1) <= '9') {
      temp = temp * 10 + s.charAt(i + 1) - '0';
      i++;
   }
   num2 = temp;
   if (c == '*') {
      stack1.push(num1 * num2);
   } else {
      stack1.push(num1 / num2);
     }
}

（5）出现“+”和“-”

加减运算的优先级没有乘除高，但是加减是平级的，所以运算是从左到右运算。具体实现是：如果符号栈里面没有元素，就先将获取的“+”或“-”存放到栈中，如果有元素，则先将元素出栈，进行运算后，放到数据栈中，再将刚刚得到的“+”或“-”符号存放到栈中，等待下一次的判断。

if (c == '+' || c == '-') {
    while (!stack2.isEmpty()) {
           char op = stack2.pop();
           int num1 = stack1.pop();
           int num2 = stack1.pop();
           if (op == '+') {
                stack1.push(num1 + num2);
           } else {
                stack1.push(num2 - num1);
             }
           }
    stack2.push(c);
}

（6）完成运算

在整个字符串遍历完后，如果符号栈中没有元素了，则返回数据栈中的那个唯一的元素，就是表达式的值，如果符号栈中还有元素，则进行最后的运算，得到的值进行返回即可

while (!stack2.isEmpty()) {
     char op = stack2.pop();
     int num1 = stack1.pop();
     int num2 = stack1.pop();
     if (op == '+') {
        stack1.push(num1 + num2);
     } else {
        stack1.push(num2 - num1);
       }
     }
return stack1.pop();

3.完整代码：

package com.algo.lesson.lesson02;

import java.util.Stack;

public class Solution_227 {

    public static void main(String[] args) {
        String s = "1*2-3/4+5*6-7*8+9/10";
        Solution_227 solution_227 = new Solution_227();
        System.out.println(solution_227.calculate(s));

    }

    public int calculate(String s) {
        int n = 0;
        Stack<Integer> stack1 = new Stack<>();
        Stack<Character> stack2 = new Stack<>();
        s = '0' + s;
        s = s.replace(" ", "");
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c >= '0' && c <= '9') {
                int x = 0;
                while (i < s.length() && s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                    x = x * 10 + s.charAt(i++) - '0';
                }
                i--;
                stack1.push(x);
            }
            if (i > 0 && (c == '*' || c == '/')) {
                int num1 = stack1.pop();
                int num2 = 0;
                while (i + 1 < s.length() && (s.charAt(i + 1) == ' ')) {
                    i++;
                }
                int temp = 0;
                while (i + 1 < s.length() && s.charAt(i + 1) >= '0' && s.charAt(i + 1) <= '9') {
                    temp = temp * 10 + s.charAt(i + 1) - '0';
                    i++;
                }
                num2 = temp;
                if (c == '*') {
                    stack1.push(num1 * num2);
                } else {
                    stack1.push(num1 / num2);
                }
            }
            if (c == '+' || c == '-') {
                while (!stack2.isEmpty()) {
                    char op = stack2.pop();
                    int num1 = stack1.pop();
                    int num2 = stack1.pop();
                    if (op == '+') {
                        stack1.push(num1 + num2);
                    } else {
                        stack1.push(num2 - num1);
                    }
                }
                stack2.push(c);
            }
        }
        while (!stack2.isEmpty()) {
            char op = stack2.pop();
            int num1 = stack1.pop();
            int num2 = stack1.pop();
            if (op == '+') {
                stack1.push(num1 + num2);
            } else {
                stack1.push(num2 - num1);
            }
        }
        return stack1.pop();
    }

}

二、带括号的计算器

不带括号的计算器已经完成了，只需要再添加一个判断括号的条件就行。

if (s.charAt(i + 1) == '(') {
    int j = i + 2;
    int count = 1;
    while (count != 0) {
        j++;
        if (s.charAt(j) == '(') {
            count++;
        } else if (s.charAt(j) == ')') {
             count--;
        }
    }
    num2 = calculate(s.substring(i + 2, j));
    i = j;
}

完整代码：

package com.algo.lesson.lesson02;

import java.util.Stack;

public class Solution_227 {

    public static void main(String[] args) {
        String s = "1*2-3/4+5*6-7*8+9/10";
        Solution_227 solution_227 = new Solution_227();
        System.out.println(solution_227.calculate(s));

    }

    public int calculate(String s) {
        int n = 0;
        Stack<Integer> stack1 = new Stack<>();
        Stack<Character> stack2 = new Stack<>();
        s = '0' + s;
        s = s.replace(" ", "");
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c >= '0' && c <= '9') {
                int x = 0;
                while (i < s.length() && s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                    x = x * 10 + s.charAt(i++) - '0';
                }
                i--;
                stack1.push(x);
            } else if (c == '+' || c == '-' || c == '(') {
                stack2.push(c);
            } else if (c == ')') {
                while (stack2.peek() != '(') {
                    char op = stack2.pop();
                    int num1 = stack1.pop();
                    int num2 = stack1.pop();
                    if (op == '+') {
                        stack1.push(num1 + num2);
                    } else {
                        stack1.push(num2 - num1);
                    }
                }
                stack2.pop(); // 弹出左括号
            } else if (c == '*' || c == '/') {
                while (!stack2.isEmpty()) {
                    char op = stack2.pop();
                    int num1 = stack1.pop();
                    int num2 = stack1.pop();
                    if (op == '+') {
                        stack1.push(num1 + num2);
                    } else {
                        stack1.push(num2 - num1);
                    }
                }
                stack2.push(c);
            }
        }
        while (!stack2.isEmpty()) {
            char op = stack2.pop();
            int num1 = stack1.pop();
            int num2 = stack1.pop();
            if (op == '+') {
                stack1.push(num1 + num2);
            } else {
                stack1.push(num2 - num1);
            }
        }
        return stack1.pop();
    }

}

代码简化：

只使用一个栈就可以实现，一些判断方法也可以直接调用Java中的方法。

感兴趣的可以自行阅读：

public class Solution {
    public int calculate(String s) {
        int result = 0;
        int num = 0;
        int sign = 1;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                num = num * 10 + (c - '0');
            } else if (c == '+' || c == '-') {
                result += sign * num;
                num = 0;
                sign = (c == '+') ? 1 : -1;
            } else if (c == '(') {
                stack.push(result);
                stack.push(sign);
                result = 0;
                sign = 1;
            } else if (c == ')') {
                result += sign * num;
                num = 0;
                result *= stack.pop();
                result += stack.pop();
            }
        }
        result += sign * num;
        return result;
    }
}

以上就是Java利用栈来实现计算器的代码，在LeetCode中也有相对应的题目，感兴趣的可以前往相应题目看一看：

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台（不带括号的计算器）

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台（带括号的计算器）文章来源地址https://www.toymoban.com/news/detail-815107.html

到了这里，关于数据结构——基本计算器的实现的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！