一、堆疊的簡介及其基本操作
堆疊的介紹
1）堆疊的英文為(stack)
2）堆疊是一個先入后出(FILO-First In Last Out)的有序串列
3）堆疊(stack)是限制線性表中元素的插入和洗掉只能在線性表的同一端進行的一種特殊線性表，允許插入和洗掉的一端，為變化的一端，稱為堆疊頂(Top),另一端為固定的一端，稱為堆疊底(Bottom).
4）根據堆疊的定義可知，最先放入堆疊中元素在堆疊底，最后放入的元素在堆疊頂，而洗掉元素剛好相反，最后放入的元素最先洗掉，最先放入的元素最后洗掉
堆疊的應用場景
1）子程式的呼叫：在跳往子程式前，會先將下個指令的地址存入到堆疊中，直到子程式執行完后再將地址取出，以回到原來的程式中，
2）處理遞回呼叫：和子程式的呼叫類似，只是除了儲存下一個指令的地址外，也將引數、區域變數等資料存入堆疊中，
3）運算式的轉換[中綴運算式轉后綴運算式]與求值(實際解決)，
4）二叉樹的呃遍歷，
5）圖形的深度優先(depth - first)搜索法，
陣列模擬堆疊
1）使用陣列來模擬堆疊
2）定義一個 top 來表示堆疊頂，初始化為 -1
3）入堆疊的操作，當有資料加入到堆疊時，top++;stack[top] = data;
4）出堆疊的操作，int value = stack[top];top--;return value
public class ArrayStackDemo {
public static void main(String[] args) {
// 測驗一下ArrayStack是否正確
// 先創建一個ArrayStack物件->表示堆疊
ArrayStack stack = new ArrayStack(4);
String key = "";
boolean loop = true;// 控制是否退出選單
Scanner scanner = new Scanner(System.in);
while (loop) {
System.out.println("show: 表示顯示堆疊");
System.out.println("exit: 退出程式");
System.out.println("push: 表示添加資料到堆疊(入堆疊)");
System.out.println("pop: 表示從堆疊取出資料(出堆疊)");
System.out.println("請輸入你的選擇");
key = scanner.next();
switch (key) {
case "show":
stack.list();
break;
case "push":
System.out.println("請輸入一個數");
int value = scanner.nextInt();
stack.push(value);
break;
case "pop":
try {
int res = stack.pop();
System.out.printf("出堆疊的資料是%d\n", res);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case "exit":
scanner.close();
loop = false;
break;
default:
break;
}
}
System.out.println("程式退出~~");
}
}
//定義一個ArrayStack表示堆疊
class ArrayStack {
private int maxSize;// 堆疊的大小
private int[] stack;// 陣列，陣列模擬堆疊，資料就放在該陣列
private int top = -1;// top表示堆疊頂，初始化為-1
// 構造器
public ArrayStack(int maxSize) {
this.maxSize = maxSize;
stack = new int[this.maxSize];
}
// 堆疊滿
public boolean isFull() {
return top == maxSize - 1;
}
// 堆疊空
public boolean isEmpty() {
return top == -1;
}
// 入堆疊-push
public void push(int value) {
// 先判斷堆疊是否滿
if (isFull()) {
System.out.println("堆疊滿");
return;
}
top++;
stack[top] = value;
}
// 出堆疊-pop,將堆疊頂的資料回傳
public int pop() {
// 先判斷堆疊是否空
if (isEmpty()) {
// 拋出例外
throw new RuntimeException("堆疊空，沒有資料~~");
}
int value = stack[top];
top--;
return value;
}
// 顯示堆疊的情況[遍歷堆疊]，遍歷時，需要從堆疊頂開始顯示資料
public void list() {
if (isEmpty()) {
System.out.println("堆疊空，沒有資料~~");
return;
}
// 需要從堆疊頂開始顯示資料
for (int i = top; i >= 0; i--) {
System.out.printf("stack[%d]=%d\n", i, stack[i]);
}
}
}堆疊實作綜合計算器【中綴運算式】
1.通過一個index值(索引)，來遍歷運算式
2.如果發現是一個數字，就直接入數堆疊
3.如果發現掃描到是一個符號，就分如下情況
3.1 如果發現當前的符號堆疊為空，就直接入堆疊
3.2 如果符號堆疊有運算子，就進行比較，如果當前的運算子的優先級小于或者等于堆疊中的運算子，就需要從數堆疊中pop出兩個數，再從符號堆疊中pop出一個符號，進行運算，將得到結果，入數堆疊，然后將當前的運算子入符號堆疊，如果當前的運算子的優先級大于戰中的運算子，就直接入符號堆疊
4.當運算式掃描完畢，就順序的從數堆疊和符號堆疊中pop出相應的數和符號，并運行，
5.最后在數堆疊只有一個數字，就是運算式的結果
public class Calculator {
public static void main(String[] args) {
// 根據前面老師思路，完成運算式的運算
String expression = "7*2*2-5+1-5+3-4";
// 創建兩個堆疊，數堆疊，一個符號堆疊
ArrayStack2 numStack = new ArrayStack2(10);
ArrayStack2 operStack = new ArrayStack2(10);
// 定義需要的相關變數
int index = 0;// 用于掃描
int num1 = 0;
int num2 = 0;
int oper = 0;
int res = 0;
char ch = ' ';// 將每次掃描得到char保存到ch
String keepNum = "";// 用于拼接多位數
// 開始while回圈的掃描expression
while (true) {
// 依次得到expression的每一個字符
ch = expression.substring(index, index + 1).charAt(0);
// 判斷ch是什么，然后做出相應的處理
if (operStack.isOper(ch)) {// 如果是運算子
// 判斷當前的符號堆疊是否為空
if (!(operStack.isEmpty())) {
// 如果符號堆疊有運算子，就進行比較，如果當前的運算子的優先級小于或者等于堆疊中的運算子，就需要從數堆疊
// 中pop出兩個數，再從符號堆疊中pop出一個符號，進行運算，將得到結果，入數堆疊，然后將當前的運算子
// 入符號堆疊
if (operStack.priority(ch) <= operStack.priority(operStack.peek())) {
num1 = numStack.pop();
num2 = numStack.pop();
oper = operStack.pop();
res = numStack.cal(num1, num2, oper);
// 把運算的結構入數堆疊
numStack.push(res);
// 然后把當前的運算子入符號堆疊
operStack.push(ch);
} else {
// 如果當前的運算子的優先級大于堆疊中的運算子，就直接入符號堆疊，
operStack.push(ch);
}
} else {
// 如果為空直接入符號堆疊
operStack.push(ch);
}
} else {// 如果是數，則直接入數堆疊
// numStack.push(ch - 48);// 掃描到的運算式是'1',需要轉為數字1//這樣不能處理多位數，改進
// 分析思路
// 1.當處理多位數時，不能發現 時一個數就立即入堆疊，因為它 可能是多位數
// 2.在處理數，需要向expression的運算式的index后再看一位，如果是數就進行掃描，如果是符號才入堆疊
// 3.因此需要定義一個變數 字串，用于拼接
// 處理多位數
keepNum += ch;
// 如果ch已經是expression的最后一位，就直接入堆疊
if (index == expression.length() - 1) {
numStack.push(Integer.parseInt(keepNum));
} else {
// 判斷下一個字符是不是數字，如果是數字，就繼續掃描，如果是運算子，則入堆疊
// 注意是看后一位，不是index++
if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) {
// 如果后一位是運算子，則入堆疊keepNum = "1" 或者 "123"
numStack.push(Integer.parseInt(keepNum));
// 重要的！！！！，keepNum清空
keepNum = "";
}
}
}
// 讓index + 1,并判斷是否掃描到expression最后，
index++;
if (index >= expression.length()) {
break;
}
}
// 當運算式掃描完畢，就順序的從數堆疊和符號堆疊中pop出相應的數和符號，并運行
while (true) {
// 如果符號堆疊為空，則計算到最后的結果，數堆疊中只有一個數字【結果】
if (operStack.isEmpty()) {
break;
}
num1 = numStack.pop();
num2 = numStack.pop();
oper = operStack.pop();
res = numStack.cal(num1, num2, oper);
numStack.push(res);// 入堆疊
}
// 將數堆疊的最后數，pop出，就是結果
int res2 = numStack.pop();
System.out.printf("運算式 %s = %d", expression, res2);
}
}
//先創建一個堆疊，直接使用前面的
//定義一個ArrayStack2表示堆疊，需要擴展功能
class ArrayStack2 {
private int maxSize;// 堆疊的大小
private int[] stack;// 陣列，陣列模擬堆疊，資料就放在該陣列
private int top = -1;// top表示堆疊頂，初始化為-1
// 構造器
public ArrayStack2(int maxSize) {
this.maxSize = maxSize;
stack = new int[this.maxSize];
}
// 增加一個方法，可以回傳當前堆疊頂的值，但是不是真正的pop
public int peek() {
return stack[top];
}
// 堆疊滿
public boolean isFull() {
return top == maxSize - 1;
}
// 堆疊空
public boolean isEmpty() {
return top == -1;
}
// 入堆疊-push
public void push(int value) {
// 先判斷堆疊是否滿
if (isFull()) {
System.out.println("堆疊滿");
return;
}
top++;
stack[top] = value;
}
// 出堆疊-pop,將堆疊頂的資料回傳
public int pop() {
// 先判斷堆疊是否空
if (isEmpty()) {
// 拋出例外
throw new RuntimeException("堆疊空，沒有資料~~");
}
int value = stack[top];
top--;
return value;
}
// 顯示堆疊的情況[遍歷堆疊]，遍歷時，需要從堆疊頂開始顯示資料
public void list() {
if (isEmpty()) {
System.out.println("堆疊空，沒有資料~~");
return;
}
// 需要從堆疊頂開始顯示資料
for (int i = top; i >= 0; i--) {
System.out.printf("stack[%d]=%d\n", i, stack[i]);
}
}
// 回傳運算子的優先級，優先級時程式員來確定，優先級使用數字表示
// 數字越大，則優先級就越高
public int priority(int oper) {
if (oper == '*' || oper == '/') {
return 1;
} else if (oper == '+' || oper == '-') {
return 0;
} else {
return -1;// 假定目前的運算式只有+，-，*，/
}
}
// 判斷是不是一個運算子
public boolean isOper(char val) {
return val == '+' || val == '-' || val == '*' || val == '/';
}
// 計算方法
public int cal(int num1, int num2, int oper) {
int res = 0;// res用于存放計算的結果
switch (oper) {
case '+':
res = num1 + num2;
break;
case '-':
res = num2 - num1;
break;
case '*':
res = num1 * num2;
break;
case '/':
res = num2 / num1;
break;
default:
break;
}
return res;
}
}二、前綴(波蘭運算式)、中綴、后綴運算式(逆波蘭運算式)
前綴運算式
1）前綴運算式又稱波蘭式，前綴運算式的運算子位于運算元之前
2）舉例說明：(3 + 4)*5 - 6對應的前綴運算式就是 - * + 3 4 5 6
中綴運算式
后綴運算式
逆波蘭計算器
1）輸入一個逆波蘭運算式，使用堆疊(Stack),計算其結果
2）支持小括號和多位數整數
中綴運算式轉為后綴運算式
逆波蘭計算器代碼：使用到了中綴運算式轉后綴運算式
public class PolandNotation {
public static void main(String[] args) {
// 完成將一個中綴運算式轉成后綴運算式的功能
// 說明
// 1. 1+((2+3)*4)-5 => 1 2 3 + 4 * + 5 -
// 2. 因為直接對str進行操作，不方便，因此先將"1+((2+3)*4)-5" => 中綴的運算式對應的List
// 即"1+((2+3)*4)-5" => ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]
// 3.將得到的中綴運算式對應的List => 后綴運算式對應的List
// 即ArrayList[1, +, (, (, 2, +, 3, ), *, 4, ), -, 5] => [1,2,3,+,4,*,+,5,-]
String expression = "1+((2+3)*4)-5";
List<String> infixExpressionList = toInfixExpressionList(expression);
System.out.println(infixExpressionList);// [1, +, (, (, 2, +, 3, ), *, 4, ), -, 5]
List<String> suffixExpressionList = parseSuffixExpressionList(infixExpressionList);
System.out.println("后綴運算式對應的List" + suffixExpressionList);
System.out.printf("expression=%d", calculate(suffixExpressionList));
/*
* // 先定義一個逆波蘭運算式 // (3 + 4) * 5 - 6 => 3 4 + 5 * 6 - //
* 說明：為了方便，逆波蘭運算式的數字和符號使用空格隔開 String suffixExcepression = "3 4 + 5 * 6 -"; // 思路
* // 1.先將"3 4 + 5 * 6 - " => 放到ArrayList中 //
* 2.將ArrayList傳遞給一個方法，遍歷ArrayList配合堆疊完成計算 List<String> list =
* getListString(suffixExcepression); System.out.println("rpnList=" + list); int
* res = calculate(list); System.out.println("計算的結果是=" + res);
*/
}
// 方法：將中綴運算式轉成對應的List
// s="1+((2+3)*4)-5";
public static List<String> toInfixExpressionList(String s) {
// 定義一個List,存放中綴運算式對應的內容
List<String> ls = new ArrayList<String>();
int i = 0;// 這是一個指標，用于遍歷中綴運算式字串
String str;// 對多位數的拼接
char c;// 每遍歷到一個字符，就放入到c
do {
// 如果c是一個非數字，就需要加入到ls
if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) < 57) {
ls.add("" + c);
i++;// i需要后移
} else {// 如果是一個數，需要考慮多位數
str = "";// 先將str置成"" '0'[48] -> '9'[57]
while (i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) < 57) {
str += c;// 拼接
i++;
}
ls.add(str);
}
} while (i < s.length());
return ls;// 回傳
}
// 方法：將得到的中綴運算式對應的List => 后綴運算式對應的List
public static List<String> parseSuffixExpressionList(List<String> ls) {
// 定義兩個堆疊
Stack<String> s1 = new Stack<String>();// 符號堆疊
// 說明：因為s2這個堆疊，在整個轉換程序中，沒有pop操作，而且后面我們還需要逆序輸出
// 因此比較麻煩，這里我們就不用Stack<String> 直接使用List<String> s2
// Stack<String> s2 = new Stack<String>();//儲存有中間結果的堆疊s2
List<String> s2 = new ArrayList<String>();// 儲存中間結果的List s2
// 遍歷ls
for (String item : ls) {
// 如果是一個數，加入s2
if (item.matches("\\d+")) {
s2.add(item);
} else if (item.equals("(")) {
s1.push(item);
} else if (item.equals(")")) {
// 如果是右括號")",則依次彈出s1堆疊頂的運算子，并壓入s2,直到遇到左括號為止，此時將這一對括號去掉
while (!s1.peek().equals("(")) {
s2.add(s1.pop());
}
s1.pop();// !!!!將 ( 彈出s1堆疊，消除小括號
} else {
// 當item的優先級小于等于s1堆疊頂運算子，將s1堆疊頂的運算子彈出并加入到s2中，再次轉到(4.1)與s1中新的堆疊頂運算子相比較
// 問題：缺少一個比較優先級高低的方法
while (s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)) {
s2.add(s1.pop());
}
// 還需要將item壓入堆疊
s1.push(item);
}
}
// 將s1中剩余的運算子依次彈出并加入s2
while (s1.size() != 0) {
s2.add(s1.pop());
}
return s2;// 注意因為是存放到List,因此按順序輸出就是對應的后綴運算式對應的List
}
// 將一個逆波蘭運算式，依次將資料和運算子放入到ArrayList中
public static List<String> getListString(String suffixExcepression) {
// 將suffixExcepression分割
String[] split = suffixExcepression.split(" ");
List<String> list = new ArrayList<String>();
for (String ele : split) {
list.add(ele);
}
return list;
}
// 完成對逆波蘭運算式的運算
/*
* 1)從左至右掃描，將3和4壓入堆疊 2)遇到 + 運算子，因此彈出4和3(4為堆疊頂元素，3為次頂元素)，計算出3+4的值，得7，再將7入堆疊 3)將5入堆疊
* 4)接下來是*運算子，因此彈出5和7，計算出7*5=35，將35入堆疊 5)將6入堆疊 6)最后是-運算子，計算出35-6得知，即29，由此得出最終結果
*/
public static int calculate(List<String> ls) {
// 創建一個堆疊，只需要一個堆疊即可
Stack<String> stack = new Stack<String>();
// 遍歷 ls
for (String item : ls) {
// 這里使用正則運算式來取出數
if (item.matches("\\d+")) {// 匹配的是多位數
// 入堆疊
stack.push(item);
} else {
// pop出兩個數，并運算，再入堆疊
// 注意接收num的數值順序與后面運算時num的順序要對應，否則結果會出錯
int num2 = Integer.parseInt(stack.pop());
int num1 = Integer.parseInt(stack.pop());
int res = 0;
if (item.equals("+")) {
res = num1 + num2;
} else if (item.equals("-")) {
res = num1 - num2;
} else if (item.equals("*")) {
res = num1 * num2;
} else if (item.equals("/")) {
res = num1 / num2;
} else {
throw new RuntimeException("運算子有誤");
}
// 把res入堆疊
stack.push("" + res);
}
}
// 最后留在stack中的資料是運算結果
return Integer.parseInt(stack.pop());
}
}
//撰寫一個類Operation可以回傳一個運算子對應的優先級
class Operation {
private static int ADD = 1;
private static int SUB = 1;
private static int MUL = 2;
private static int DIV = 2;
// 寫一個方法，回傳對應的優先級數字
public static int getValue(String operation) {
int result = 0;
switch (operation) {
case "+":
result = ADD;
break;
case "-":
result = SUB;
break;
case "*":
result = MUL;
break;
case "/":
result = DIV;
break;
default:
System.out.println("不存在該運算子");
break;
}
return result;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/300245.html
標籤：其他