堆棧的應(yīng)用

棧的特點(diǎn): 后進(jìn)先出

進(jìn)制轉(zhuǎn)換

package com.bjpowernode.stack;
/**
 * 使用棧完成進(jìn)制轉(zhuǎn)換
 * @author 北京動(dòng)力節(jié)點(diǎn)老崔
 */
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));
		
	}
	/**
	 * 把一個(gè)十進(jìn)制整數(shù) num轉(zhuǎn)換為decimal指定的進(jìn)制
	 * @param num		接收十進(jìn)制整數(shù)
	 * @param decimal	指定進(jìn)制
	 * @return		返回num這個(gè)整數(shù)對(duì)應(yīng) 的decimal進(jìn)制的字符串
	 */
	public static String convert(int num,  int decimal) {
		MyArrayStack stack = new MyArrayStack(); 		//保存余數(shù)
		int  remainder = num % decimal ; 		//余數(shù)
		while( num != 0 ) {
			stack.push( remainder ); 		//余數(shù)壓棧
			num = num / decimal;
			remainder = num % decimal ; 
		}
		
		//出棧,余數(shù)倒序
		StringBuilder sb = new StringBuilder();
		while( !stack.isEmpty() ) {
			sb.append( stack.pop() );
		}
		
		return sb.toString();
	}

}

檢測(cè)表達(dá)式中括弧是否匹配

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

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

對(duì)于任意一個(gè)左括弧都需要有一個(gè)相應(yīng) 的右括弧匹配, 最早出現(xiàn)的右括弧應(yīng)該與最早出現(xiàn)的左括弧匹配. 符合棧的特點(diǎn)。

算法:

• 讀取整個(gè)表達(dá)式, 如果是左括弧就直接入棧,等待與它對(duì)應(yīng)的右括弧出現(xiàn);

• 如果是右括弧, 則與當(dāng)前棧頂?shù)淖罄ɑ∨袛嗍欠衿ヅ?/p>

• 如果不匹配,說明表達(dá)式不合法

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

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

package com.bjpowernode.stack;
/**
 * 檢測(cè)表達(dá)式中的括弧是否匹配
 * @author 北京動(dòng)力節(jié)點(diǎn)老崔
 */
public class TestBracketMatch {

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

}

算術(shù)表達(dá)式的求值

1、四則運(yùn)算的規(guī)則 :

先乘除后加減

先括弧內(nèi)再括弧外

從左到右進(jìn)行運(yùn)算

2、表達(dá)式:

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、算法思路:

① 定義兩個(gè)棧, 一個(gè)存儲(chǔ)操作符operator, 一個(gè)存儲(chǔ)操作數(shù)operand

② 讀取表達(dá)式, 如果是操作數(shù)就存儲(chǔ)到operand操作數(shù)棧

如果是操作符

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

• 把操作符棧中的棧頂操作符與當(dāng)前操作符進(jìn)行優(yōu)先級(jí)比較；

當(dāng)前操作符優(yōu)先級(jí)高, 操作符入棧；

當(dāng)前操作符優(yōu)先級(jí)低(棧頂操作符優(yōu)先級(jí)高), 彈出棧頂操作符,從操作數(shù)棧中彈出兩個(gè)操作數(shù)進(jìn)行運(yùn)算, 把運(yùn)算結(jié)果存儲(chǔ)到操作數(shù)棧中, 繼續(xù)判斷當(dāng)前操作符與棧頂操作符的優(yōu)先級(jí)。

③ 遍歷完整個(gè)表達(dá)式, 兩個(gè)棧都不為空, 依次彈出操作符opertor棧中的運(yùn)算符與操作數(shù)棧中的兩個(gè)操作數(shù)進(jìn)行計(jì)算 , 把結(jié)果再存儲(chǔ)到操作數(shù)棧中。

④ 如果操作符棧不為空, 或者操作數(shù)棧中的數(shù)不止有一個(gè), 則表達(dá)式錯(cuò)誤。

package com.bjpowernode.stack;
/**
 * 使用棧計(jì)算算術(shù)表達(dá)式的值
 * @author 北京動(dòng)力節(jié)點(diǎn)老崔
 */
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 );
	}
	//定義方法計(jì)算 指定表達(dá)式的值 :  6834+3+(6-10+2*3)*43
	private static double calculate(String expression) {
		MyArrayStack operatorStack = new MyArrayStack(); 	//存儲(chǔ)操作符
		MyArrayStack operandStack = new MyArrayStack(); 	//存儲(chǔ)操作數(shù)
		//遍歷表達(dá)式中的操作數(shù)與操作符
		for( int i = 0 ;  i < expression.length() ; i++ ) {
			char cc = expression.charAt(i);
			//如果cc是數(shù)字
			if ( Character.isDigit(cc)) {
				//取出操作數(shù)
				StringBuilder sb = new StringBuilder();
				//只要是數(shù)字就是操作數(shù)的一部分
				while( Character.isDigit(cc)) {
					sb.append(cc);			//6
					i++; 					//取下個(gè)字符
					if ( i >= expression.length() ) { 	//表達(dá)式結(jié)束 
						break;
					}
					cc = expression.charAt(i); 		//取下個(gè)字符
				}
				//操作數(shù)入棧
				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();
					//判斷棧中運(yùn)算符與當(dāng)前運(yùn)算符的優(yōu)先級(jí)
					if ( compareOperator(op1, cc) < 0 ) {
						//當(dāng)前運(yùn)算符的優(yōu)先級(jí)高于棧頂運(yùn)算符的優(yōu)先級(jí)
						operatorStack.push(cc);
						break;
					}else if ( compareOperator(op1, cc) == 0) {
						//當(dāng)前運(yùn)算符的優(yōu)先級(jí)等于 棧頂運(yùn)算符的優(yōu)先級(jí), 只有一種 情況, 左一半小括弧遇到右一半小括弧的情況
						operatorStack.pop() ; 		//棧中左一半小括弧出棧
						break;
					}else { 	//棧頂運(yùn)算符優(yōu)先級(jí)高
						//取出兩個(gè)操作數(shù)
						if (operandStack.isEmpty()) {
							throw new RuntimeException("表達(dá)式錯(cuò)誤");
						}
						double num1 = Double.parseDouble(operandStack.pop().toString());
						if (operandStack.isEmpty()) {
							throw new RuntimeException("表達(dá)式錯(cuò)誤");
						}
						double num2 = Double.parseDouble(operandStack.pop().toString());
						//取棧頂運(yùn)算符
						char  operator = (char) operatorStack.pop();
						//計(jì)算   num2 op  num1
						double result = compute(operator , num2, num1 );
						//把結(jié)果存儲(chǔ)到操作數(shù)棧中
						operandStack.push(result);
						//如果當(dāng)前操作符棧為空, 新的操作符入棧
						if ( operatorStack.isEmpty()) {
							operatorStack.push(cc);
							break;
						}
					}
				}
				
			}
		}
		
		//當(dāng)表達(dá)式 遍歷完后, 如果操作符棧不為空, 需要繼續(xù)計(jì)算 
		while( !operatorStack.isEmpty()) {
			char operator = (char) operatorStack.pop();
			//如果操作數(shù)棧為空, 表達(dá)式錯(cuò)誤
			if (operandStack.isEmpty()) {
				throw new RuntimeException("表達(dá)式錯(cuò)誤");
			}
			double num1 = Double.parseDouble(operandStack.pop().toString());
			if (operandStack.isEmpty()) {
				throw new RuntimeException("表達(dá)式錯(cuò)誤");
			}
			double num2 = Double.parseDouble(operandStack.pop().toString());
			double result = compute(operator , num2, num1 );
			operandStack.push(result);
		}
		//當(dāng)操作符棧為空, 操作數(shù)棧中多于一個(gè)數(shù), 表達(dá)式錯(cuò)誤
		if ( operandStack.getSize() > 1) {
			throw new RuntimeException("表達(dá)式錯(cuò)誤");
		}
		
		return Double.parseDouble(operandStack.pop().toString());
	}
	//計(jì)算 num1  op num2 表達(dá)式的值
	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;
	}
	//判斷兩個(gè)運(yùn)算符的優(yōu)先級(jí) ,如果op1優(yōu)先級(jí)高返回正數(shù), op2優(yōu)先級(jí)高返回負(fù)數(shù)
	private static int compareOperator(char op1, char op2) {
		if ( op1 == '+' || op1 == '-') {
			if (op2 == '*' || op2 =='/' || op2 =='(') {
				//第一個(gè)運(yùn)算符是 +-, 第二個(gè)運(yùn)算符是 * / (
				return -1;
			}
		}
		if (op1 =='*' || op1 =='/') {
			if ( op2 =='(') {
				//第一個(gè)是*/, 第二個(gè)是(
				return -1;
			}
		}
		if ( op1 == '(') {
			if (op2 == ')') {
				return 0;
			}else {
				return -1;
			}
		}
		return 1;
	}

}