算法提高——栈的使用

本文主要是介绍算法提高——栈的使用，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

数据结构：栈

一、概念

　　对于学过数据结构的人来说，栈的概念应该不陌生，栈是一种先进后出的数据结构，可以把栈想象成一摞盘子，不管是加盘子还是拿盘子，都要从最上面拿。关于栈的详细概念，可以查阅严蔚敏的《数据结构》这本书。

二、例题

　　1、简单计算器

　　　　题目描述：读入一个只包含+,-,*,/的非负整数计算表达式，计算该表达式的值

　　　　输入样例：30\90-26=97-5-5-13/88*6+51/29+79*87+57*92

　　　　样例输出：12178.21

　　　　算法思路：通过栈实现先乘除，后加减，这里需要引入后缀表达式的概念，后缀表达式就是把一次运算的操作符放后边，运算数放前面，这样作的好处是不需要括号实现对运算顺序的控制，当然前提是先将带括号的中缀表达式（常见表达式）给出，转换成后缀表达式。后缀表达式更利与程序计算。

　　　　算法描述：

　　　　　　（1）先写出后缀表达式，定义一个队列，用来存放后缀表达式，一个栈，用来暂存操作符

　　　　　　（2）对于数字可以直接加入后缀表达式中，对于运算符，如果栈空就直接将运算符压入栈中，如果栈中有元素，就进行判断，当前入栈元素优先级大于栈顶元素优先级，就　　　　　　                        压入栈中，如果当前元素优先级小于等于栈顶元素优先级，就将栈顶元素出栈到后缀表达式中，直到入栈元素优先级大于栈顶元素

　　　　　　（3）重复步骤（2）

　　　　　　（4）当转换成后缀表达式时就可以进行计算操作，

　　　　　　　　　　从左向右扫描后缀表达式（队列出队操作），对于操作数，直接入栈，对于操作符，就出栈两个操作数，进行运算后再入栈，重复此操作，直到队空，此时栈顶元素          　　　　　　就是结果

说明：此处因为408从未考过算法题，所以不再给出代码，但是可以参考该思路编写代码。注意对数字读入时多位数字作为整体进行读入。

这篇关于算法提高——栈的使用的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！