數(shù)據(jù)結(jié)構(gòu)——基本計(jì)算器的實(shí)現(xiàn)

這篇具有很好參考價(jià)值的文章主要介紹了數(shù)據(jù)結(jié)構(gòu)——基本計(jì)算器的實(shí)現(xiàn)。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問(wèn)。

????????

一、不帶括號(hào)的計(jì)算器

1.整體思想：

2.具體細(xì)節(jié)：

? ? ? ? （1）字符串中有空格

? ? ? ? （2）表達(dá)式開(kāi)頭可能是符號(hào)

? ? ? ? （3）將數(shù)字放在第一個(gè)棧中

? ? ? ? （4）出現(xiàn)“*”和“/”

? ? ? ? （5）出現(xiàn)“+”和“-”

????????（6）完成運(yùn)算

3.完整代碼：

二、帶括號(hào)的計(jì)算器

完整代碼：

代碼簡(jiǎn)化：

????????計(jì)算器是我們生活中經(jīng)常會(huì)用到的物品，現(xiàn)在我們需要利用棧和隊(duì)列的知識(shí)，來(lái)自己編寫(xiě)一個(gè)程序，來(lái)實(shí)現(xiàn)計(jì)算器的基本功能。

一、不帶括號(hào)的計(jì)算器

? ? ? ? 在運(yùn)算中，我們需要遵循運(yùn)算符號(hào)的優(yōu)先級(jí)，先乘除，后加減，有括號(hào)的先運(yùn)算括號(hào)里面的。由此可見(jiàn)，在加上括號(hào)后，難度會(huì)有點(diǎn)兒大，所以我們現(xiàn)在先完成不帶括號(hào)的計(jì)算器，后面在實(shí)現(xiàn)帶括號(hào)的計(jì)算器。

1.整體思想：

? ? ? ? 表達(dá)式以字符串形式給予的，所以我們需要在字符上進(jìn)行操作。我們可以創(chuàng)建兩個(gè)棧，一個(gè)用來(lái)存放數(shù)據(jù)元素，一個(gè)用來(lái)存放符號(hào)元素。在符號(hào)棧里面獲取到符號(hào)后，將數(shù)據(jù)棧里面的兩個(gè)元素出棧進(jìn)行操作，然后再放回到數(shù)據(jù)棧里面。如此操作，最后便能得到這個(gè)表達(dá)式的運(yùn)算結(jié)果。

2.具體細(xì)節(jié)：

? ? ? ? 在代碼實(shí)現(xiàn)的過(guò)程中，會(huì)出現(xiàn)一些問(wèn)題，接下來(lái)我會(huì)一一解答并附上解決的代碼。

? ? ? ? （1）字符串中有空格

可以在所有運(yùn)算前，將字符串里的所有空格刪除或替換。（replace（）方法來(lái)替換字符串里的空格）

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

? ? ? ? （2）表達(dá)式開(kāi)頭可能是符號(hào)

在字符串前加一個(gè)"0"（如果是"-"開(kāi)頭，在運(yùn)算時(shí)，沒(méi)有與之匹配的前一項(xiàng)數(shù)據(jù)元素，會(huì)有報(bào)錯(cuò)）

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

? ? ? ? （3）將數(shù)字放在第一個(gè)棧中

數(shù)字可能會(huì)不止一位，所以我們需要判斷數(shù)字的位數(shù)，然后再進(jìn)行存放

   char c = s.charAt(i);//循環(huán)得到字符串的每一個(gè)字符
if (c >= '0' && c <= '9') {//判斷字符是不是數(shù)字
   int x = 0;
   while (i < s.length() && s.charAt(i) >= '0' && s.charAt(i) <= '9') {
/*
循環(huán)遍歷，如果下一個(gè)字符依舊是數(shù)字，就將前面的字符乘10作為上一位，加后面的字符
-"0"是為了將字符轉(zhuǎn)為數(shù)字（減的是ASKII碼值，例如"0"-"0"就是0的ASKII減去0的ASKII，得到的數(shù)也就是0）
*/
       x = x * 10 + s.charAt(i++) - '0';//得到多位數(shù)的數(shù)字
   }
   i--;//在判斷是否為數(shù)字時(shí)得到的字符會(huì)多加一位，會(huì)出現(xiàn)跳過(guò)下一個(gè)字符的情況，所以要對(duì)索引進(jìn)行減1的操作
   stack1.push(x);
 }

? ? ? ? （4）出現(xiàn)“*”和“/”

乘除需要先進(jìn)行運(yùn)算，運(yùn)算時(shí)需要獲取后面的元素和剛剛?cè)霔５脑?。在獲取后面的元素時(shí)也需要進(jìn)行判斷元素的位數(shù)，才能進(jìn)行運(yùn)算。

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）出現(xiàn)“+”和“-”

加減運(yùn)算的優(yōu)先級(jí)沒(méi)有乘除高，但是加減是平級(jí)的，所以運(yùn)算是從左到右運(yùn)算。具體實(shí)現(xiàn)是：如果符號(hào)棧里面沒(méi)有元素，就先將獲取的“+”或“-”存放到棧中，如果有元素，則先將元素出棧，進(jìn)行運(yùn)算后，放到數(shù)據(jù)棧中，再將剛剛得到的“+”或“-”符號(hào)存放到棧中，等待下一次的判斷。

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）完成運(yùn)算

在整個(gè)字符串遍歷完后，如果符號(hào)棧中沒(méi)有元素了，則返回?cái)?shù)據(jù)棧中的那個(gè)唯一的元素，就是表達(dá)式的值，如果符號(hào)棧中還有元素，則進(jìn)行最后的運(yùn)算，得到的值進(jìn)行返回即可

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();
    }

}

二、帶括號(hào)的計(jì)算器

? ? ? ? 不帶括號(hào)的計(jì)算器已經(jīng)完成了，只需要再添加一個(gè)判斷括號(hào)的條件就行。

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(); // 彈出左括號(hào)
            } 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();
    }

}

代碼簡(jiǎn)化：

只使用一個(gè)棧就可以實(shí)現(xiàn)，一些判斷方法也可以直接調(diào)用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利用棧來(lái)實(shí)現(xiàn)計(jì)算器的代碼，在LeetCode中也有相對(duì)應(yīng)的題目，感興趣的可以前往相應(yīng)題目看一看：

力扣（LeetCode）官網(wǎng) - 全球極客摯愛(ài)的技術(shù)成長(zhǎng)平臺(tái)（不帶括號(hào)的計(jì)算器）

力扣（LeetCode）官網(wǎng) - 全球極客摯愛(ài)的技術(shù)成長(zhǎng)平臺(tái)（帶括號(hào)的計(jì)算器）文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-815107.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)——基本計(jì)算器的實(shí)現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！