博客

栈的应用

  • Post author:
  • Post category:其他


由于栈结构具有后进先出的固有特性，致使栈称为程序设计中的有用工具。


1.数制转换

十进制数N和其他d进制数的转换是计算机实现计算的基本问题，其解决方法很多，其中一个简单算法基于下列原理：

N = (N div d) * d + N mod d(其中：div为整除运算，mod为求余运算)

例如，(2007)

10

= (3727)

8

，其运算过程如下：

进制转换运算过程

可以看到上述过程是从低位到高位产生8进制的各个数位，然后从高位到低位进行输出，结果数位的使用具有后出现先使用的特点，因此生成的结果数位可以使用一个栈来存储，然后从栈顶开始依次输出即可得到相应的转换结果。

下述算法实现了十进制数转八进制数，并打印结果。其中，对于栈，我们使用上一节中实现的

ArrayStack

： 

public class Conversion {
    public static void conversion(int N){
        ArrayStack<Integer> stack = new ArrayStack<>();
        while( N != 0){
            stack.push(N % 8);
            N /= 8;
        }
        while(!stack.isEmpty()){
            System.out.print(stack.pop());
        }
    }

    public static void main(String[] args) {
        conversion(2007);
    }
}

运行该程序，输出结果： 

3727


2.括号匹配检验

假设表达式中包含三种括号：圆括号、方括号和花括号，并且它们可以任意嵌套。例如

{[()]()[{}]}

或

[{()}([])]

等为正确格式，而

{[}()]

或

[({)]

为不正确的格式。那么怎么检测表达式是否正确呢？

这个问题可以用“期待的急迫程度”这个概念来描述。对表达式中的每一个左括号都期待一个相应的右括号与之匹配，表达式中越迟出现并且没有得到匹配的左括号期待匹配的程度越高。不是期待出现的右括号则是不正确的。它具有天然的后进先出的特点。

于是我们可以设计算法：算法需要一个栈，在读入字符的过程中，如果是左括号，则直接入栈，等待相匹配的同类右括号；如果是右括号，且与当前栈顶左括号匹配，则将栈顶左括号出栈，如果不匹配则属于不合法的情况。另外，如果碰到一个右括号，而堆栈为空，说明没有左括号与之匹配，则非法。那么，当字符读完的时候，如果是表达式合法，栈应该是空的，如果栈非空，那么则说明存在左括号没有相应的右括号与之匹配，也是非法的情况。

下述算法实现了对该表达式的括号匹配检验： 

public class Match {
    public static boolean match(String s){
        ArrayStack<Character> stack = new ArrayStack<>();
        for(int i = 0;i<s.length();i++){
            char c = s.charAt(i);
            switch (c) {
            case ')':
                if(!stack.isEmpty() && stack.pop() == '('){
                    break;
                }else{
                    return false;
                }
            case ']':
                if(!stack.isEmpty() && stack.pop() == '['){
                    break;
                }else{
                    return false;
                }
            case '}':
                if(!stack.isEmpty() && stack.pop() == '{'){
                    break;
                }else{
                    return false;
                }
            default:
                stack.push(c);
                break;
            }
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        System.out.println(match("{[()]()[{}]}"));
        System.out.println(match("{[()]}}"));
    }
}

输出结果： 

true
false


3.迷宫求解

求迷宫从入口到出口的所有路径是一个经典的程序设计问题。由于计算机解迷宫时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。

为了保证在任何位置都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此在迷宫求解时应用“栈”也就是自然而然的事情了。

在计算机中，我们可以用一个二维数组来表示一个迷宫，如下图所示：

这里写图片描述
这里写图片描述

我们使用字符1来表示迷宫中的墙体，即灰色的方块；使用字符0来表示可以通过的道路，即白色的方块。

求解迷宫的算法思想可以描述为： 

初始化，将起点加入堆栈；
while(堆栈不为空){
    取出栈顶位置为当前位置；
    如果 当前位置是终点，
    则 使用堆栈记录的路径标记从起点至终点的路径；
    否则{
        按照从下、右、上、左的顺序将当前位置下一个可以探索的位置入栈；
        如果 当前位置的四周均不通
        则 当前位置出栈；
    }
}

所谓当前位置

可通

，指的是

未曾走到过的通道块

，即要求该位置不但是通道块，而且不在当前路径上（否则所求的路径就是简单路径），也不是曾经纳入过路径的通道块（否则只能在死胡同内转悠）。

下述代码实现了对该迷宫的求解： 

/**
 * 迷宫通道类，一个Cell代表地图上的一个方块
 * @author Gavin
 *
 */
class Cell {
    private int x; // 单元所在行
    private int y; // 单元所在列
    private char c; // 字符，通道对应'0'，墙对应'1'
    private boolean isVisited;// 是否访问过

    public Cell(int x, int y, char c, boolean isVisited) {
        super();
        this.x = x;
        this.y = y;
        this.c = c;
        this.isVisited = isVisited;
    }

    public char getC() {
        return c;
    }

    public void setC(char c) {
        this.c = c;
    }

    public boolean isVisited() {
        return isVisited;
    }

    public void setVisited(boolean isVisited) {
        this.isVisited = isVisited;
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Cell other = (Cell) obj;
        if (x != other.x)
            return false;
        if (y != other.y)
            return false;
        return true;
    }

    @Override
    public String toString() {
        return this.getC() + "("+this.getX()+", "+this.getY() + ")";
    }
}

/**
 * 迷宫求解类
 * @author Gavin
 *
 */
public class Maze {

    public static void main(String[] args) {
        char maze[][] = { { '1', '1', '1', '1', '1', '1', '1', '1', '1', '1' },
                { '1', '0', '0', '1', '1', '1', '0', '0', '1', '1' },
                { '1', '0', '0', '1', '1', '0', '0', '1', '0', '1' },
                { '1', '0', '0', '0', '0', '0', '0', '1', '0', '1' },
                { '1', '0', '0', '0', '0', '1', '1', '0', '0', '1' },
                { '1', '0', '0', '1', '1', '1', '0', '0', '0', '1' },
                { '1', '0', '0', '0', '0', '1', '0', '1', '0', '1' },
                { '1', '0', '1', '1', '0', '0', '0', '1', '0', '1' },
                { '1', '1', '0', '0', '0', '0', '1', '0', '0', '1' },
                { '1', '1', '1', '1', '1', '1', '1', '1', '1', '1' }, };
        mazeExit(maze, 8, 8, 1, 7);
    }

    /**
     * 求解迷宫
     * @param maze 迷宫的字符数组
     * @param in_x 起点x坐标
     * @param in_y 起点y坐标
     * @param out_x 终点x坐标
     * @param out_y 终点y坐标
     */
    public static void mazeExit(char maze[][], int in_x, int in_y, int out_x, int out_y) {
        Cell[][] cells = createMaze(maze);
        printMaze(cells);
        Cell start = cells[in_x][in_y];
        Cell end = cells[out_x][out_y];
        ArrayStack<Cell> stack = new ArrayStack<>();
        stack.push(start);
        start.setVisited(true);
        while (!stack.isEmpty()) {
            Cell now = stack.peek();
            if (now.equals(end)) {
                // 找到路径
                int x = out_x;
                int y = out_y;
                while(!stack.isEmpty()){
                    Cell cell = stack.pop();
                    // 要注意的是，只有和上一次的cell相邻的cell才是路径上的通道
                    if(Math.abs(cell.getX()-x) + Math.abs(cell.getY()- y) <= 1){
                        cell.setC('*');
                    }
                    x = cell.getX();
                    y = cell.getY();
                }
                System.out.println("找到路径：");
                printMaze(cells);
                return;
            } else {
                // 向四个方向探索
                boolean isDead = true;
                for (int i = 0; i < 4; i++) {
                    Cell next_cell = getCell(cells, now, i);
                    if (isValid(next_cell)) {
                        next_cell.setVisited(true);
                        stack.push(next_cell);
                        isDead = false;
                    }
                }
                // 四个方向都不能走，则该点为死胡同，出栈
                if(isDead){
                    stack.pop();
                }
            }
        }
        System.out.println("找不到路径");
    }

    /**
     * 判断一个cell是否是通道
     * @param cell
     * @return
     */
    public static boolean isValid(Cell cell) {
        return cell.getC() == '0' && !cell.isVisited();
    }

    /**
     * 根据方向得到下一个cell
     * @param cells
     * @param now
     * @param direction
     * @return
     */
    public static Cell getCell(Cell[][] cells, Cell now, int direction) {
        int x = now.getX();
        int y = now.getY();
        Cell cell = null;
        switch (direction) {
        case 0:
            // 向下
            cell =  cells[x + 1][y];
            break;
        case 1:
            // 向右
            cell =  cells[x][y + 1];
            break;
        case 2:
            // 向上
            cell =  cells[x - 1][y];
            break;
        case 3:
            // 向左
            cell =  cells[x][y - 1];
            break;
        }
        return cell;
    }

    /**
     * 根据输入的二维char数组创建二维Cell数组
     * 
     * @param maze
     *            二维char数组
     * @return
     */
    private static Cell[][] createMaze(char[][] maze) {
        Cell[][] cells = new Cell[maze.length][maze[0].length];
        for (int i = 0; i < maze.length; i++) {
            for (int j = 0; j < maze[i].length; j++) {
                char c = maze[i][j];
                Cell cell = new Cell(i, j, c, false);
                cells[i][j] = cell;
            }
        }
        return cells;
    }

    /**
     * 打印迷宫
     * 
     * @param cells
     */
    private static void printMaze(Cell[][] cells) {
        for (int i = 0; i < cells.length; i++) {
            for (int j = 0; j < cells[i].length; j++) {
                System.out.print(cells[i][j].getC() + " ");
            }
            System.out.println();
        }
    }
}

程序用星号

*

标记路径，输出结果如下： 

1 1 1 1 1 1 1 1 1 1 
1 0 0 1 1 1 0 0 1 1 
1 0 0 1 1 0 0 1 0 1 
1 0 0 0 0 0 0 1 0 1 
1 0 0 0 0 1 1 0 0 1 
1 0 0 1 1 1 0 0 0 1 
1 0 0 0 0 1 0 1 0 1 
1 0 1 1 0 0 0 1 0 1 
1 1 0 0 0 0 1 0 0 1 
1 1 1 1 1 1 1 1 1 1 

找到路径：
1 1 1 1 1 1 1 1 1 1 
1 0 0 1 1 1 * * 1 1 
1 0 0 1 1 * * 1 0 1 
1 * * * * * 0 1 0 1 
1 * 0 0 0 1 1 0 0 1 
1 * 0 1 1 1 * * * 1 
1 * * * * 1 * 1 * 1 
1 0 1 1 * * * 1 * 1 
1 1 0 0 0 0 1 0 * 1 
1 1 1 1 1 1 1 1 1 1

上述代码还需要注意的是，因为迷宫四周有墙，因此从当前位置向四周探索时，数组下标不会越界；如果迷宫四周没有墙，则在向四周探索时，要验证位置的下标是否越界。


4.表达式求值 & 中缀表达式转后缀表达式

表达式求值是程序设计语言中的一个最基本问题。它的实现是栈应用的又一个典型例子。这里介绍一种简单直观、广为使用的算法，通常称为“算符优先法”。

要把一个表达式翻译成正确求值的一个机器指令序列，或者直接对表达式求值，首先要能够正确解释表达式。例如要对下述表达式求值： 

4+（6-10+2*2）*2

首先，要了解算术四则运算的规则。即：

  • （1）先乘除，后加减；
  • （2）从左算到右
  • （3）先括号内，后括号外

由此，这个算术表达式的计算顺序应为： 

4+（6-10+2*2）*2 = 4+（-4+2*2）*2 = 4+（-4+4）*2 = 4+0*2 = 4+0 = 4

任何一个表达式都是由操作数（operand）、运算符（operator）和界限符（delimiter）组成。界限符也就是括号等，运算符包括加减乘除，以及更复杂的求余、三角函数等等。这里我们只讨论比较简单的算术表达式，只包括加减乘除四种运算符。

我们把运算符和界限符统称为算符，根据上述3条运算规则，在运算每一步中，任意两个相继出现的算符θ1和θ2之间的优先关系至多是下面三种关系之一：

  • θ1 < θ2，θ1的优先权低于θ2
  • θ1 = θ2，θ1的优先权等于θ2
  • θ1 > θ2，θ1的优先权大于θ2

下表定义了这种优先关系：

θ1 \ θ2 + – * / ( )

+
 		> > < < < >

–
 		> > < < < >
* < < > > < >

/
 		< < > > < >

(
 		< < < < < =

)
 		> > > > >

由规则（3），+、-、*和/为θ1时的优先级均低于“(”但高于右括号”)”，由规则（2），当θ1 = θ2时，令θ1 > θ2。

基于上述的论述，首先，我们来讨论使用算符优先算法来实现表达式的求值。

为实现该算法，我们需要使用两个工作栈。一个称作OPTR，用以寄存运算符；另一个称作OPND，用以寄存操作数或运算结果。算法的基本思想是：

  • （1）首先置操作数栈和操作符栈为空栈

  • （2）依次读入表达式中的每个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先权后作相应操作。

    1.若该运算符优先权大于栈顶运算符优先权则该运算符直接进OPTR栈；反之若运算符优先权小于栈顶运算符的优先权，则弹出栈顶运算符，并从操作数OPND栈弹出两个数进行该栈顶运算符的运算，运算结果再加入OPND操作数栈。

    2.循环往复地进行第1步判断。直到将该操作符加入OPTR操作符栈

  • （3）表达式读取结束，若两个栈都不为空，则依次弹出OPTR栈中的运算符和OPND栈中的两个操作数，进行运算后，将运算结果在加入OPND栈。直到OPTR栈为空，OPND栈只剩下一个元素，则该元素就是运算结果。

  • （4）中间出现差错，比如最后OPND栈剩下不止一个数，则视为表达式出错。

下述算法实现了该表达式求值的算法： 

import java.util.EmptyStackException;

public class Evaluate {

    public static void main(String[] args) {
        System.out.println(new Evaluate().evaluate("4+(6-10+2*2)*2"));
    }

    /**
     * 表达式求值
     * 
     * @param expression
     *            表达式
     * @return 返回double型的计算结果
     */
    public double evaluate(String expression) {
        ArrayStack<Double> OPND_stack = new ArrayStack<>();// 操作数栈
        ArrayStack<Character> OPTR_stack = new ArrayStack<>(); // 操作符栈
        // 遍历这个表达式
        for (int i = 0; i < expression.length(); i++) {
            char c = expression.charAt(i);
            // 如果当前字符是数字，也就是操作数
            if (Character.isDigit(c) || c == '.') {
                StringBuilder stringBulider = new StringBuilder();
                // 操作数的拼接，包括小数点
                while (i < expression.length() && (Character.isDigit(c = expression.charAt(i)) || c == '.')) {
                    stringBulider.append(c);
                    i++;
                }
                // 操作数入栈
                OPND_stack.push(Double.valueOf(stringBulider.toString()));
                // 跳过本次循环，i的值已经增加过，所以要减去
                i--;
                continue;
            } else {
                // 当前的字符是操作符
                outer: while (!OPTR_stack.isEmpty()) {
                    switch (precede(OPTR_stack.peek(), c)) {
                    case '<':
                        // 栈顶运算符小于该运算符，该运算符直接入栈
                        OPTR_stack.push(c);
                        break outer;
                    case '=':
                        // 栈顶运算符等于该运算符，只有一种情况，左右括号匹配，弹出左括号
                        OPTR_stack.pop();
                        break outer;
                    case '>':
                        // 栈顶运算符大小该运算符
                        char optr = OPTR_stack.pop();
                        // 如果有多余的操作符却没有操作数可以计算了，那么说明表达式错误
                        try {
                            double opnd2 = OPND_stack.pop();
                            double opnd1 = OPND_stack.pop();
                            OPND_stack.push(operate(opnd1, optr, opnd2));
                        } catch (EmptyStackException e) {
                            System.err.println("表达式有误0！");
                            System.exit(0);
                        }
                        break;
                    }
                }
                // 第一次栈为空的情况，直接入栈。还有退栈直至栈为空的情况，当前操作符也需要入栈
                if (OPTR_stack.isEmpty()) {
                    OPTR_stack.push(c);
                }
            }
        }
        while (!OPTR_stack.isEmpty()) {
            char optr = OPTR_stack.pop();
            // 如果有多余的操作符却没有操作数可以计算了，那么说明表达式错误
            try {
                double opnd2 = OPND_stack.pop();
                double opnd1 = OPND_stack.pop();
                OPND_stack.push(operate(opnd1, optr, opnd2));
            } catch (EmptyStackException e) {
                System.err.println("表达式有误！");
                System.exit(0);
            }
        }
        if (OPND_stack.size() == 1) {
            return OPND_stack.pop();
        } else {
            System.err.println("表达式有误！");
            System.exit(0);
        }
        return 0;
    }

    /**
     * 运算
     * 
     * @param opnd1
     *            操作数1
     * @param optr
     *            操作符
     * @param opnd2
     *            操作符2
     * @return 运算结果
     */
    private double operate(double opnd1, char optr, double opnd2) {
        switch (optr) {
        case '+':
            return opnd1 + opnd2;
        case '-':
            return opnd1 - opnd2;
        case '*':
            return opnd1 * opnd2;
        case '/':
            return opnd1 / opnd2;
        }
        return 0;
    }

    /**
     * 比较两个运算符的优先权大小
     * 
     * @param θ1
     * @param θ2
     * @return
     */
    public char precede(char θ1, char θ2) {
        if (θ1 == '+' || θ1 == '-') {
            if (θ2 == '+' || θ2 == '-' || θ2 == ')') {
                return '>';
            } else {
                return '<';
            }
        } else if (θ1 == '*' || θ1 == '/') {
            if (θ2 == '(') {
                return '<';
            } else {
                return '>';
            }
        } else if (θ1 == '(') {
            if (θ2 == ')') {
                return '=';
            } else {
                return '<';
            }
        }else if(θ1 == ')'){
            return '>';
        }
        return '>';
    }
}

程序运行正确。输出： 

4.0

要注意的是，上述程序支持小数的输入，但暂不支持负数，对负数要进一步处理，这里不作赘述。

上述算法即为表达式求值的过程，用到了两个栈，一个操作数栈OPND，一个操作符栈OPRT。

那么还有一种程序设计需求是先将中缀表达式转换成后缀表达式，再对后缀表达式进行求值。所谓中缀表达式就是人类能正常阅读的算术表达式，就像我们上述例子中的输入一样：

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

。而后缀表达式是让计算机读的，有了后缀表达式之后再求值就非常简单。

而中缀表达式转后缀表达式的过程与上类似，只不过在依次读入字符的过程中遇到操作符先不求值，对于优先级高的栈顶操作符，将之弹出加入操作数队列（队列也是一种数据结构）即可，最后输出整个队列，就是后缀表达式。

这里我们用

StringBuilder

代替队列，对上述算法稍作修改，便可实现中缀表达式转后缀表达式: 

public class Suffix {
    public static void main(String[] args) {
        System.out.println(new Suffix().infixToSuffix("4+(6-10+2*2)*2"));
    }

    /**
     * 中缀表达式转后缀表达式
     * 
     * @param expression
     *            表达式
     * @return 返回后缀表达式
     */
    public String infixToSuffix(String expression) {
        ArrayStack<Character> OPTR_stack = new ArrayStack<>();// 操作符栈
        StringBuilder suffix = new StringBuilder();
        // 遍历这个表达式
        for (int i = 0; i < expression.length(); i++) {
            char c = expression.charAt(i);
            // 如果当前字符是数字，也就是操作数
            if (Character.isDigit(c) || c == '.') {
                StringBuilder stringBulider = new StringBuilder();
                // 操作数的拼接，包括小数点
                while (i < expression.length() && (Character.isDigit(c = expression.charAt(i)) || c == '.')) {
                    stringBulider.append(c);
                    i++;
                }
                suffix.append(stringBulider.toString()+" ");
                // 跳过本次循环，i的值已经增加过，所以要减去
                i--;
                continue;
            } else {
                // 当前的字符是操作符
                outer: while (!OPTR_stack.isEmpty()) {
                    switch (precede(OPTR_stack.peek(), c)) {
                    case '<':
                        // 栈顶运算符小于该运算符，该运算符直接入栈
                        OPTR_stack.push(c);
                        break outer;
                    case '=':
                        // 栈顶运算符等于该运算符，只有一种情况，左右括号匹配，弹出左括号
                        OPTR_stack.pop();
                        break outer;
                    case '>':
                        // 栈顶运算符大小该运算符
                        char optr = OPTR_stack.pop();
                        suffix.append(optr);
                        suffix.append(" ");
                        break;
                    }
                }
                // 第一次栈为空的情况，直接入栈。还有退栈直至栈为空的情况，当前操作符也需要入栈
                if (OPTR_stack.isEmpty()) {
                    OPTR_stack.push(c);
                }
            }
        }
        while (!OPTR_stack.isEmpty()) {
            char optr = OPTR_stack.pop();
            suffix.append(optr);
            suffix.append(" ");
        }
        return suffix.toString();
    }

    /**
     * 比较两个运算符的优先权大小
     * 
     * @param θ1
     * @param θ2
     * @return
     */
    public static char precede(char θ1, char θ2) {
        if (θ1 == '+' || θ1 == '-') {
            if (θ2 == '+' || θ2 == '-' || θ2 == ')') {
                return '>';
            } else {
                return '<';
            }
        } else if (θ1 == '*' || θ1 == '/') {
            if (θ2 == '(') {
                return '<';
            } else {
                return '>';
            }
        } else if (θ1 == '(') {
            if (θ2 == ')') {
                return '=';
            } else {
                return '<';
            }
        }else if(θ1 == ')'){
            return '>';
        }
        return '>';
    }
}

程序输出： 

4 6 10 - 2 2 * + 2 * +

这便是输入的中缀表达式所对应的后缀表达式，后缀表达式是没有括号的。

之后再对后缀表达式求值的话就比较简单了，只需要再用一个栈，依次读入后缀表达式的每个字符，如果是操作数则入栈，如果是操作符则弹出栈顶两个元素进行运算，将运算结果再入栈，最后的栈顶元素就是运算结果。其实也就是表达式求值的计算部分。


版权声明：本文为ggGavin原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。