堆棧的應用

棧的特點: 后進先出

進制轉換

package com.bjpowernode.stack;
/**
 * 使用棧完成進制轉換
 * @author 北京動力節點老崔
 */
public class TestBaseConversion {

	public static void main(String[] args) {
		// 
		System.out.println( convert(100, 2));
		System.out.println( convert(100, 8));
//		System.out.println( convert(100, 16));
		
	}
	/**
	 * 把一個十進制整數 num轉換為decimal指定的進制
	 * @param num		接收十進制整數
	 * @param decimal	指定進制
	 * @return		返回num這個整數對應 的decimal進制的字符串
	 */
	public static String convert(int num,  int decimal) {
		MyArrayStack stack = new MyArrayStack(); 		//保存余數
		int  remainder = num % decimal ; 		//余數
		while( num != 0 ) {
			stack.push( remainder ); 		//余數壓棧
			num = num / decimal;
			remainder = num % decimal ; 
		}
		
		//出棧,余數倒序
		StringBuilder sb = new StringBuilder();
		while( !stack.isEmpty() ) {
			sb.append( stack.pop() );
		}
		
		return sb.toString();
	}

}

檢測表達式中括弧是否匹配

假設表達式中包含三種括弧: 小括弧(), 中括弧[], 大括弧{}, 這三種括弧可以任意嵌套；

(3+5) * [ 3-6] -{23/4}+([{}])

對于任意一個左括弧都需要有一個相應 的右括弧匹配, 最早出現的右括弧應該與最早出現的左括弧匹配. 符合棧的特點。

算法:

• 讀取整個表達式, 如果是左括弧就直接入棧,等待與它對應的右括弧出現;

• 如果是右括弧, 則與當前棧頂的左括弧判斷是否匹配

• 如果不匹配,說明表達式不合法

• 如果是右括弧, 棧已空, 表示不合法

• 讀完整個表達式, 堆棧不空, 表示有左括弧沒匹配上, 表達式不合法; 讀完整個表達式,棧是空的表示所有括弧都能匹配。

package com.bjpowernode.stack;
/**
 * 檢測表達式中的括弧是否匹配
 * @author 北京動力節點老崔
 */
public class TestBracketMatch {

	public static void main(String[] args) {
		// 
		System.out.println( bracketMatch("([{}])"));
		System.out.println( bracketMatch("([{(}])"));
		System.out.println( bracketMatch("([{}]))"));
	}
	
	//檢測expression表達式 中的括弧是否匹配
	public static boolean bracketMatch(String expression) {
		MyArrayStack stack = new MyArrayStack()	;			//保存左括弧
		//遍歷整個表達式, 如果是左括弧就入棧, 如果是右括弧,就出棧進行判斷是否匹配
		for( int i = 0 ;  i < expression.length(); i++) {
			//取出表達式的每個字符
			char cc = expression.charAt(i); 
			switch (cc) {
			case '(':
			case '[':
			case '{':
				stack.push(cc);  	//左括弧入棧, Java可以自動裝箱與拆箱
				break;
			case '}':
				if ( !stack.isEmpty() && stack.pop().equals('{')) {
					break;
				}else {
					return false;
				}
			case ']':
				if ( !stack.isEmpty() && stack.pop().equals('[')) {
					break;
				}else {
					return false;
				}
			case ')':
				if ( !stack.isEmpty() && stack.pop().equals('(')) {
					break;
				}else {
					return false;
				}
				
			}
		}
		
		//表達式遍歷完后,如果棧是空的,表示括弧匹配, 
		if (stack.isEmpty()) {
			return true;
		}else {
			return false;
		}
		
	}

}

算術表達式的求值

1、四則運算的規則 :

先乘除后加減

先括弧內再括弧外

從左到右進行運算

2、表達式:

4 + 3 + ( 6 - 10 + 2*3) * 4

7 + ( 6 - 10 + 2*3) * 4

7 + ( -4 + 2*3) * 4

7 + ( -4 + 6) * 4

7 + 2 * 4

7 + 8

15

3、算法思路:

① 定義兩個棧, 一個存儲操作符operator, 一個存儲操作數operand

② 讀取表達式, 如果是操作數就存儲到operand操作數棧

如果是操作符

• 操作符棧是空, 直接入棧

• 把操作符棧中的棧頂操作符與當前操作符進行優先級比較；

當前操作符優先級高, 操作符入棧；

當前操作符優先級低(棧頂操作符優先級高), 彈出棧頂操作符,從操作數棧中彈出兩個操作數進行運算, 把運算結果存儲到操作數棧中, 繼續判斷當前操作符與棧頂操作符的優先級。

③ 遍歷完整個表達式, 兩個棧都不為空, 依次彈出操作符opertor棧中的運算符與操作數棧中的兩個操作數進行計算 , 把結果再存儲到操作數棧中。

④ 如果操作符棧不為空, 或者操作數棧中的數不止有一個, 則表達式錯誤。

package com.bjpowernode.stack;
/**
 * 使用棧計算算術表達式的值
 * @author 北京動力節點老崔
 */
public class TestCalculateExpression {

	public static void main(String[] args) {
		// 
		String expression = "4+3+(6-10+2*3)*4";
		double result = calculate( expression );
		System.out.println( result );
	}
	//定義方法計算 指定表達式的值 :  6834+3+(6-10+2*3)*43
	private static double calculate(String expression) {
		MyArrayStack operatorStack = new MyArrayStack(); 	//存儲操作符
		MyArrayStack operandStack = new MyArrayStack(); 	//存儲操作數
		//遍歷表達式中的操作數與操作符
		for( int i = 0 ;  i < expression.length() ; i++ ) {
			char cc = expression.charAt(i);
			//如果cc是數字
			if ( Character.isDigit(cc)) {
				//取出操作數
				StringBuilder sb = new StringBuilder();
				//只要是數字就是操作數的一部分
				while( Character.isDigit(cc)) {
					sb.append(cc);			//6
					i++; 					//取下個字符
					if ( i >= expression.length() ) { 	//表達式結束 
						break;
					}
					cc = expression.charAt(i); 		//取下個字符
				}
				//操作數入棧
				operandStack.push(sb.toString());
				//修正i變量的值
				i--;
//				System.out.println( sb );
			}else { 	//如果是操作符
				//4+3+(6-10+2*3)*4
				//1)棧為空, 直接把操作符入棧
				if (operatorStack.isEmpty()) {
					operatorStack.push(cc);
					continue;
				}
				//2)操作符棧不為空的情況
				while( !operatorStack.isEmpty()) {
					char op1 = (char) operatorStack.peek();
					//判斷棧中運算符與當前運算符的優先級
					if ( compareOperator(op1, cc) < 0 ) {
						//當前運算符的優先級高于棧頂運算符的優先級
						operatorStack.push(cc);
						break;
					}else if ( compareOperator(op1, cc) == 0) {
						//當前運算符的優先級等于 棧頂運算符的優先級, 只有一種 情況, 左一半小括弧遇到右一半小括弧的情況
						operatorStack.pop() ; 		//棧中左一半小括弧出棧
						break;
					}else { 	//棧頂運算符優先級高
						//取出兩個操作數
						if (operandStack.isEmpty()) {
							throw new RuntimeException("表達式錯誤");
						}
						double num1 = Double.parseDouble(operandStack.pop().toString());
						if (operandStack.isEmpty()) {
							throw new RuntimeException("表達式錯誤");
						}
						double num2 = Double.parseDouble(operandStack.pop().toString());
						//取棧頂運算符
						char  operator = (char) operatorStack.pop();
						//計算   num2 op  num1
						double result = compute(operator , num2, num1 );
						//把結果存儲到操作數棧中
						operandStack.push(result);
						//如果當前操作符棧為空, 新的操作符入棧
						if ( operatorStack.isEmpty()) {
							operatorStack.push(cc);
							break;
						}
					}
				}
				
			}
		}
		
		//當表達式 遍歷完后, 如果操作符棧不為空, 需要繼續計算 
		while( !operatorStack.isEmpty()) {
			char operator = (char) operatorStack.pop();
			//如果操作數棧為空, 表達式錯誤
			if (operandStack.isEmpty()) {
				throw new RuntimeException("表達式錯誤");
			}
			double num1 = Double.parseDouble(operandStack.pop().toString());
			if (operandStack.isEmpty()) {
				throw new RuntimeException("表達式錯誤");
			}
			double num2 = Double.parseDouble(operandStack.pop().toString());
			double result = compute(operator , num2, num1 );
			operandStack.push(result);
		}
		//當操作符棧為空, 操作數棧中多于一個數, 表達式錯誤
		if ( operandStack.getSize() > 1) {
			throw new RuntimeException("表達式錯誤");
		}
		
		return Double.parseDouble(operandStack.pop().toString());
	}
	//計算 num1  op num2 表達式的值
	private static double compute(char operator, double num1, double num2) {
		switch (operator) {
		case '+':
			return num1 + num2;
			
		case '-':
			return num1 - num2;
			
		case '*':
			return num1 * num2;
			
		case '/':
			return num1 / num2;
		}
		return 0;
	}
	//判斷兩個運算符的優先級 ,如果op1優先級高返回正數, op2優先級高返回負數
	private static int compareOperator(char op1, char op2) {
		if ( op1 == '+' || op1 == '-') {
			if (op2 == '*' || op2 =='/' || op2 =='(') {
				//第一個運算符是 +-, 第二個運算符是 * / (
				return -1;
			}
		}
		if (op1 =='*' || op1 =='/') {
			if ( op2 =='(') {
				//第一個是*/, 第二個是(
				return -1;
			}
		}
		if ( op1 == '(') {
			if (op2 == ')') {
				return 0;
			}else {
				return -1;
			}
		}
		return 1;
	}

}