数据结构与算法分析--栈的应用

事实上，可以利用数据结构中的 “栈”来做许多实用的操作。 下面就来列举几个，各位有用可以直接拿去用。

 

一、 利用栈来进行进制数的转换。

直接上代码说话:

package com.base.stack;

import java.util.Stack;

/**
 * 使用栈来转换数字
 * 10进制转换为2进制
 * @author gogole_09
 *
 */
public class Demo1 {
	public static void main(String[] args) {
		System.out.println(toBinary(1123));
	}
	
	public static String toBinary(int num){
		String result="";
		Stack s=new Stack();
		while(num!=0){
			s.push(num%2);//取摸，将余数压入栈
			num=num/2;    //消去十进制数的最后一位
		}
		while(!s.isEmpty()){
			result+=s.pop();//出栈
		}
		return result;
	}
}

 

二、做后缀表达式运算（何为后缀表达式--代码中说明）：

 

package com.base.stack;

import java.util.Stack;

/**
 * 用作后缀表达式求解
 * 
 * @author gogole_09
 * 
 * 何为后缀表达式：
 * 
 * 举例如下： 假设我们需要一个便携式计算器来计算一趟外出购物的花费（包括当地的税款，假设为1.06） 买了3个货品 A:4.99 B:5.99 C:6.99
 * 设B不需要缴税，具体计算如下： 4.99*1.06+5.99+6.99*1.06= 问题出在这里。
 * 简单计算器会给你19.37,而科学计算器会给你18.69. 显然，我们需要的结果是18.69,实际科学计算器计算时，一般会自动包含括号，
 * 所以当我们处理这类问题时，我们的思路如下： 
   1) 4.99*1.06 存入 A1 
     2) 5.99 + A1 -->结果存入A1 
     3) 6.99*1.06 存入 A2 
     4) A1+A2 -->结果存入A1
 * 
 * 故后缀表达式如下： 【4.99 1.06 * 5.99 + 6.99 1.06 * + 】
 */
public class PostfixDemo {
	/**(以整数为例)
	 * 以后缀表达式： 6 5 3 2 + 8 * + 3 + * 为例
	 * 
	 * @param args
	 * @throws Exception 
	 */
	public static void main(String[] args)  {
		PostTest();
	}

	
	public static void PostTest() {
		//"34 24 23 2 4 2 + 8 * + 3 +*";
		String postFix ="6 5 3 2 + 8 * + 3 + *";
		Stack result = new Stack();//栈对象
		int res=0;
//分组是为了能够处理多位数字 ,
//如果是"6532+8*+3+*",则无法判断到底是6,5,3,2还是6532
		String[] str=postFix.split(" ");
		
		for (int i = 0; i < str.length; i++) {
			//是否为运算符
			if("+-*/".indexOf(str[i])==-1)
				result.push(str[i]);
			else{
				//栈为空，则无法后续操作
				if(!result.isEmpty()){
					//将两个操作数出栈
					int num1=Integer.parseInt(result.pop().toString());
					int num2=Integer.parseInt(result.pop().toString());
					//获取运算值
					res=operation(num1, num2,str[i].charAt(0));
					
					if(res!=-1){
						result.push(res);
					}
				}
			}
		}
		System.out.println(result.pop());
	}
	
	
	/**
	 * 具体运算方法
	 * @param num1
	 * @param num2
	 * @param flag
	 * @return
	 */
	public static int operation(int num1, int num2,char flag) {
		int result=0;
		switch (flag) {
		case '+':
			result=num1+num2;
			break;
		case '-':
			result=num1-num2;
			break;
		case '*':
			result=num1*num2;
			break;
		case '/':
			result=num1/num2;
			break;
		default:
			result=-1;
			break;
		}
		return result;
	}
}

 

三、将中缀转换成后缀表达式。

 

package com.base.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;


/**
 * 
 * @author gogole_09
 * 转换过程包括用下面的算法读入中缀表达式的操作数、操作符和括号：
 * 初始化一个空堆栈，将结果字符串变量置空。 
 * 从左到右读入中缀表达式，每次一个字符。 
 * 如果字符是操作数，将它添加到结果字符串。 
 * 如果字符是个操作符，弹出（pop）操作符，直至遇见开括号（opening parenthesis）、优先级较低的操作符或者同一优先级的右结合符号。把这个操作符压入（push）堆栈。 
 * 如果字符是个开括号，把它压入堆栈。 
 * 如果字符是个闭括号（closing parenthesis），在遇见开括号前，弹出所有操作符，然后把它们添加到结果字符串。 
 * 如果到达输入字符串的末尾，弹出所有操作符并添加到结果字符串。
 */
public class FontToBackPostFix {
	
	public static void main(String[] args) {
		FontToBackPostFix fix=new FontToBackPostFix();
		List<String> list=fix.fontPostExp("2+3+(3+2)+3*4#");
		for(String s:list){
			System.out.println(s);
		}
	}
	
	public List<String> fontPostExp(String str){//将中缀表达式转化成为后缀表达式
		
		List<String> postfix=new ArrayList<String>();//存放着转化后后缀表达式的链表
		StringBuffer numberBuf=new StringBuffer();//用来保存数字
		Stack<Character> opStack=new Stack<Character>();//保存操作符
		
		char ch,preChar;
		//压入标识符
		opStack.push('#');
		try {
			for (int i = 0; i < str.length(); ) {
				ch=str.charAt(i);
				
				switch (ch) {
				case '+':
				case '-':
				case '*':
				case '/':
					preChar=opStack.peek();//查看栈顶对象而不移除它					
					//如果栈里面的操作符优先级比当前的大，则把栈中优先级大的都添加到后缀表达式列表中
					while(priority(preChar)>=priority(ch)){
						postfix.add(""+preChar);
						opStack.pop();//出栈
						preChar=opStack.peek();
					}
					opStack.push(ch);
					i++;
					break;
				case '(':
					//左括号直接压栈
					opStack.push(ch);
					i++;
					break;
				case ')':
					char c = opStack.pop();   
                    while(c != '('){   
                        postfix.add("" + c);   
                        c = opStack.pop();   
                    }   
                    i++;   
                    break;   
				case '#':
					char c1;
					while(!opStack.isEmpty()){
						c1=opStack.pop();
						if(c1!='#'){
							postfix.add(""+c1);
						}
					}
					i++;
					break;
				case ' ':
				case '\t':
					i++;
					break;
				default:
					//不是操作符,如果是数字
					if(Character.isDigit(ch)){
						while(Character.isDigit(ch)){
							numberBuf.append(ch);
							ch=str.charAt(i++);
						}
						postfix.add(numberBuf.toString());
						numberBuf=new StringBuffer();
					}else{
						
					}
					break;
				}
			}
		} catch (Exception e) {
			e.printStackTrace();
		}
		return postfix;
		
		
	}
	
	/**
	 * 设置优先级
	 */
	public int priority(char op){
		switch (op) {
		case '+':
		case '-':
			return 1;
		case '*':
		case '/':
			return 2;
		case '(':
		case '#':
			return 0;
		}
		return -1;
		
	}
}

关于中缀转后缀有参考 http://fuliang.iteye.com/blog/172233 处。