⑤算法與資料結構-java-棧

⑤棧

實際需求

請輸入一個表達式

計算式:[722-5+1-5+3-3] 點選計算【如下圖】

請問: 計算機底層是如何運算得到結果的？ 注意不是簡單的把算式列出運算,因為我們看這個算式 7 * 2 * 2 - 5,

但是計算機怎麼了解這個算式的(對計算機而言，它接收到的就是一個字元串)，我們讨論的是這個問題。-> 棧

棧的介紹

1）棧的英文為(stack)

2）棧是一個先入後出(FILO-First In Last Out)的有序清單。

3）棧(stack)是限制線性表中元素的插入和删除隻能線上性表的同一端進行的一種特殊線性表。允許插入和删除的一端，為變化的一端，稱為棧頂(Top)，另一端為固定的一端，稱為棧底(Bottom)。

4）根據棧的定義可知，最先放入棧中元素在棧底，最後放入的元素在棧頂，而删除元素剛好相反，最後放入的元素最先删除，最先放入的元素最後删除

棧的應用場景

1）子程式的調用：在跳往子程式前，會先将下個指令的位址存到堆棧中，直到子程式執行完後再将位址取出，以回到原來的程式中。

2）處理遞歸調用：和子程式的調用類似，隻是除了儲存下一個指令的位址外，也将參數、區域變量等資料存入堆棧中。

3）表達式的轉換[中綴表達式轉字尾表達式]與求值(實際解決)。

4）二叉樹的周遊。

5）圖形的深度優先(depth一first)搜尋法。

數組模拟棧

代碼：

public class ArrayStackDemo {
	public static void main(String[] args) {
		// 測試一下ArrayStack是否正确
		// 先建立一個ArrayStack的對象
		ArrayStack stack = new ArrayStack(4);
		String key = "";
		boolean loop = true;// 控制是否退出菜單
		Scanner input = new Scanner(System.in);
		while (loop) {
			System.out.println("show：表示顯示棧");
			System.out.println("exit:退出程式");
			System.out.println("push:表示添加資料到棧");
			System.out.println("pop:表示從棧取出");
			key = input.next();
			switch (key) {
			case "show":
				stack.list();
				break;
			case "push":
				System.out.println("輸入一個數：");
				int value = input.nextInt();
				stack.push(value);
				break;
			case "pop":
				try {
					int res = stack.pop();
					System.out.println(res);
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
				break;
			case "exit":
				input.close();
				loop = false;
				break;
			default:
				break;
			}
		}
		System.out.println("程式退出！");
	}

}

class ArrayStack {

	private int maxSize;// 棧的大小
	private int[] stack;// 數組，數組模拟棧，資料就放在數組中
	private int 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;
	}

	// 入棧
	public void push(int value) {
		// 先判斷是否滿
		if (isFull()) {
			System.out.println("棧滿");
			return;
		} else {
			top++;
			stack[top] = value;
		}
	}

	// 出棧将棧頂的資料傳回
	public int pop() {
		if (isEmpty()) {
			// 抛出異常
			throw new RuntimeException("棧空，沒有資料");

		} else {
			int value = stack[top];
			top--;
			return value;
		}
	}

	// 周遊棧,周遊時需要從開始顯示資料

	public void list() {
		if (isEmpty()) {
			System.out.println("棧空，沒有資料");
			return;
		} else {
			for (int i = top; i >= 0; i--) {
				System.out.println(stack[i]);
			}
		}
	}
}
           

棧實作綜合電腦

代碼：

//棧模拟電腦
public class Calculator {
	public static void main(String[] args) {
		// 根據前面的思路，完成表達式的一個運算
		String expression = "70+20*6-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) {
			// 依次得到expres的每一個字元
			ch = expression.substring(index, index + 1).charAt(0);
			// 判斷ch是什麼，然後進行相應的判斷
			if (operStack.isOper(ch)) {// 如果為運算符
				// 判斷目前的符号棧是否為空
				if (!operStack.isEmpty()) {
					// 如果不為空，比較
					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.當處理多位數時，不能發現是一個數就立刻入棧，因為他可能是多位數
				// 2.在處理數時，需要向expression的表達式的index後看一位，是不是數，如果是繼續掃描，直到符号才入棧
				// 3.是以我們需要定義一個變量 字元串，用于拼接
				// 處理多位數
				keepNum += ch;

				// 如果ch已經是expression的最後一位，就直接入棧
				if (index == expression.length() - 1) {
					numStack.push(Integer.parseInt(keepNum));

				} else {

					// 判斷下一個字元是不是數字，如果是數字，就繼續掃描

					if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) {
						// 如果後一位是運算符就入棧
						numStack.push(Integer.parseInt(keepNum));
						// 重要的清空!!!!!!
						keepNum = "";
					}
				}
			}
			// 讓index+1,并判斷是否掃描到expression
			index++;
			if (index >= expression.length()) {
				break;
			}
		}
		// 當表達式掃描完畢，就順序的從符号棧和數字棧中運作
		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.println(res2);
	}
}

//先建立一個棧
//定義一個ArrayStack2表示棧
class ArrayStack2 {
	private int maxSize;// 棧的大小
	private int[] stack;// 數組，數組模拟棧，資料就放在數組中
	private int top = -1;

	// 構造器
	public ArrayStack2(int maxSize) {
		this.maxSize = maxSize;
		stack = new int[this.maxSize];
	}

	// 增加一個方法，傳回棧頂的值，不是真正的出棧
	public int peek() {
		return stack[top];
	}

	// 棧滿
	public boolean isFull() {
		return top == maxSize - 1;
	}

	// 棧空
	public boolean isEmpty() {
		return top == -1;
	}

	// 入棧
	public void push(int value) {
		// 先判斷是否滿
		if (isFull()) {
			System.out.println("棧滿");
			return;
		} else {
			top++;
			stack[top] = value;
		}
	}

	// 出棧将棧頂的資料傳回
	public int pop() {
		if (isEmpty()) {
			// 抛出異常
			throw new RuntimeException("棧空，沒有資料");

		} else {
			int value = stack[top];
			top--;
			return value;
		}
	}

	// 周遊棧,周遊時需要從開始顯示資料

	public void list() {
		if (isEmpty()) {
			System.out.println("棧空，沒有資料");
			return;
		} else {
			for (int i = top; i >= 0; i--) {
				System.out.println(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;
		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;
	}

}

           

補充：字首、中綴、字尾表達式(逆波蘭表達式)

字首表達式的計算機求值

從右至左掃描表達式，遇到數字時，将數字壓入堆棧，遇到運算符時，彈出棧頂的兩個數，用運算符對它們做相應的計算（棧頂元素 和

次頂元素），并将結果入棧；重複上述過程直到表達式最左端，最後運算得出的值即為表達式的結果

例如: (3+4)×5-6 對應的字首表達式就是 - × + 3 4 5 6 , 針對字首表達式求值步驟如下:

1）從右至左掃描，将6、5、4、3壓入堆棧

2）遇到+運算符，是以彈出3和4（3為棧頂元素，4為次頂元素），計算出3+4的值，得7，再将7入棧

3）接下來是×運算符，是以彈出7和5，計算出7×5=35，将35入棧

4）最後是-運算符，計算出35-6的值，即29，由此得出最終結果

中綴表達式

1）中綴表達式就是常見的運算表達式，如(3+4)×5-6

2）中綴表達式的求值是我們人最熟悉的，但是對計算機來說卻不好操作(前面我們講的案例就能看的這個問題)，是以，在計算結果時，往往會将中綴表達式轉成其它表達式來操作(一般轉成字尾表達式.)

字尾表達式

1）字尾表達式又稱逆波蘭表達式,與字首表達式相似，隻是運算符位于操作數之後

2）中舉例說明： (3+4)×5-6 對應的字尾表達式就是 3 4 + 5 × 6 –

3） 再比如:

字尾表達式的計算機求值

從左至右掃描表達式，遇到數字時，将數字壓入堆棧，遇到運算符時，彈出棧頂的兩個數，用運算符對它們做相應的計算（次頂元素 和棧頂元素），并将結果入棧；重複上述過程直到表達式最右端，最後運算得出的值即為表達式的結果

例如: (3+4)×5-6 對應的字尾表達式就是 3 4 + 5 × 6 - , 針對字尾表達式求值步驟如下:

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，由此得出最終結果

中綴表達式轉換為字尾表達式

大家看到，字尾表達式适合計算式進行運算，但是人卻不太容易寫出來，尤其是表達式很長的情況下，是以在開發中，我們需要将中綴表達式轉成字尾表達式。

具體步驟如下:

1）初始化兩個棧：運算符棧s1和儲存中間結果的棧s2；

2）從左至右掃描中綴表達式；

3）遇到操作數時，将其壓s2；

4）遇到運算符時，比較其與s1棧頂運算符的優先級：

①如果s1為空，或棧頂運算符為左括号“(”，則直接将此運算符入棧；

②否則，若優先級比棧頂運算符的高，也将運算符壓入s1；

③否則，将s1棧頂的運算符彈出并壓入到s2中，再次轉到(4-1)與s1中新的棧頂運算符相比較；

5）遇到括号時：(1) 如果是左括号“(”，則直接壓入s1(2) 如果是右括号“)”，則依次彈出s1棧頂的運算符，并壓入s2，直到遇到左括号為止，此時将這一對括号丢棄

6）重複步驟2至5，直到表達式的最右邊

7）将s1中剩餘的運算符依次彈出并壓入s2

8）依次彈出s2中的元素并輸出，結果的逆序即為中綴表達式對應的字尾表達式

舉例說明:

将中綴表達式“1+((2+3)×4)-5”轉換為字尾表達式的過程如下

是以結果為

“1 2 3 + 4 × + 5 –”