栈的特点和应用

栈的特点和队列的特点很相似,队列是先进先出的,栈刚好相反,栈是先进后出的,栈中数据的出栈和入栈都只在同一个口

应用:计算器的实现

数组实现栈的思路

  1. 创建一个栈
  2. 编写出栈,入栈,栈是否满,是否空,遍历栈的方法

代码实现

package cn.rlfit.stack;


import javax.management.RuntimeErrorException;

public class StackDemo {

	/**
	 * 栈的实现:
	 * 1. 栈的特点和队列相似,先进后出,使用数组模拟实现栈
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
	}
}
class StackTest{
//	定义变量
	int top = 0;
	int[] arrayStack;
//	初始化栈
	public StackTest(int maxSize) {
		arrayStack = new int[maxSize];
	}
//	遍历栈
	public void list() {
		if(isEmpty()) {
			throw new RuntimeErrorException(null, "栈空无法遍历");
		}
		for(int i = top;i<arrayStack.length;i--)
		System.out.printf("stack[%d] = %d",i,arrayStack[i]);
	}
//	出栈
	public void pop() {
		if(isEmpty()) {
			throw new RuntimeErrorException(null,"栈空");
		}
		top--;
	}
//	入栈
	public void push(int data) {
		if(isFull()) {
			throw new RuntimeErrorException(null, "栈满无法添加");
		}
		top++;
		arrayStack[top] = data;
		
	}
//	栈满
	public boolean isFull() {
		return top == arrayStack.length;
	}
//	栈空
	public boolean isEmpty() {
		return top == 0;
	}
	
}

逆波兰表达式

概念

逆波兰表达式是波兰逻辑学家 J.Lukasiewicz 于1929年提出的,这种表达式是将运算符都置于数值的后面,所以也叫后缀表达式。

特点

运算符号永远在数值的后面
如普通表达式为 2+3,因为运算符在数值中间,所以这种表达式也叫中缀表达式,而逆波兰表达式写法是 23+(将运算符写在数值后面)。
运算符的置后顺序是由运算顺序决定的
如(1+2)*(3+4),逆波兰表达式为 12+34+ *,而不是 1234++ *,因为运算顺序是先计算(1+2),然后计算(3+4),最后再将两个结果相乘。所以顺序就是 12+,然后 34+,最后一个 。而不是无脑的将所有数值置前,符号置后。

举例

普通表达式 逆波兰表达式

2*8+16/2	2,8,*,16,2,/,+
28+(16-2)	28,16,2,-,+
8=10-2	8,10,2,-,=

注意:逆波兰表达式一定要注意运算符号的置后顺序,否则是计算不出来结果的。

意义

逆波兰表达式的一个重要作用就是,可以将复杂的运算转换为依靠简单的操作就可以计算出结果的简单表达式。
上面这句话怎么理解昵?简单表达式是什么,简单的操作又是什么?

简单的表达式
还是拿上面的例子来说,(1+2)*(3+4),这是一个既有加法,又有乘法的复杂运算表达式,如果用数组接收,然后转换为逆波兰表达式为 [1,2,’+’,3,4,’+’,’ * '],是不是看上去就是一个简单的表达式。

简单的操作
简单的操作指的就是有了表达式之后,就要开始运算。这里就跟前面提到的数据结构之栈有关联。通过利用栈的特点,在逆波兰表达式中,遇到 ‘+’,‘-’,‘*’,‘/’ 运算符号就把栈中的前两个数值拿出来进行计算,否则将元素(非运算符号)压入栈中,如此反复,最后在栈中剩下的元素就是计算结果。

逆波兰表达式的代码实现

    //1.创建一个栈结构
    function Stack() {
        var arr = [];
        this.push  = function (item) {
           arr.push(item);
        };
        this.pop  = function (item) {
           return  arr.pop(item);
        };
        this.size = function () {
           return  arr.length;
        };
        return arr;
    };
    //2.计算逆波兰表达式
    function calc_exp(exp) {
        var stack = new Stack();
        for(var i = 0;i< exp.length;i++){
            var item = exp[i];
            if(["+","-","*","/"].indexOf(item)>= 0){
                var str1 = stack.pop();
                var str2 = stack.pop();
                var str3= str2 + item + str1;
                stack.push(parseInt(eval(str3)))
            }else {
                stack.push(item);
            }
        }
        console.log(stack[0])
    };
    //3.参数
    var arr1= [2,8,'*',16,2,'/','+'];//普通表达式为 2*8+16/2
    var arr2=[28,16,2,'-','+'];//普通表达式为 28+(16-2)
    //4.验证
    calc_exp(arr1);//24
    calc_exp(arr2);//42