微波EDA网,见证研发工程师的成长!
首页 > 硬件设计 > 嵌入式设计 > 栈的经典运用

栈的经典运用

时间:12-01 来源:互联网 点击:
栈是计算机术语中比较重要的概念,实质上栈就是一段内存区域,但是栈满足一定的特性,那就是只有一个口,具有先入后出的特性,这种特性在计算机中有很广泛的运用。其实在程序员无时无刻不在运用栈,函数的调用是我们间接使用栈的最好例子,因此可以说栈的一个最重要的运用就是函数的调用。但是栈的运用还不止这些,还有很多,其中几个典型的运行如下:判断平衡符号,实现表达式的求值(也就是中缀表达式转后缀表达式的问题以及后缀表达式求值问题),在路劲探索中实现路劲的保存也可以说是栈的经典运用之一。具体的问题具体分析,只要满足先入后出特性的问题都能找到现成的数据结构---栈。

本文采用C++中的vector实现栈结构,然后利用栈实现判断平衡符号,实现中缀表达式到后缀表达式的转换,并依据栈实现简单的整数加减乘除运算。

首先栈的实现,由于在C++中采用了vector来代替原始的数组操作,这种比较方便的容器能较好的实现数组的功能,当然栈也可以采用链表实现,但是我认为链表没有数组直观,而且在实际的计算机里也是采用连续的存储空间作为栈空间的,因此选择Vector。主要实现三个操作,push、pop以及为空判断。基本的形式如下:

#ifndef __MYSTACK_H_H_
#define __MYSTACK_H_H_

#include "myvector.h"

namespace myspace
{
template
class Stack
{
public:
Stack(){}
void push(const Object &x)
{
objects.push_back(x);
}

const Object &pop()
{
int len;
if(!isempty())
{
objects.pop_back();
len = objects.size();
return objects[len];
}
}

bool isempty()const
{
return (objects.size() == 0);
}

int size()
{
return objects.size();
}
private:
Vector objects;
};
}

#endif

实现了简单的栈类,接下来采用栈实现一些简单的运用。

符号的平衡问题
在语言中往往需要判断一些符号是否是成对出现的,比如<>,{},[],(),通常在C++中也只有这几种对称问题,如何让判断符号的对称也是很多代码判断的首要任务。当然实现的方式是多种多样的,采用栈的实现会相对更加简单。基本的实现思路如下:
假设在读入一串字符串以后,如果遇到对称符号的左边部分,则将其压入栈中,当遇到对称符号的右边部分,则弹出栈中的一个对象,实现比对,如果是对称的,则说明当前的符号是平衡的,如果不对称,则说明当前字符串是不平衡的,当字符串读完以后,如果所有的符号都是平衡的,栈中此时应该就是为空,通过判断栈中是否为空,说明字符串是否是符号平衡的。
依据上面实现的栈类,实现符号平衡判断的过程比较简单,如下所示:

bool isbalance(const string &str)
{
string::size_type len = str.size();

Stack stack;

for(string::size_type i = 0; i < len ; ++ i)
{
/*first selection*/
if(str[i] == [ || str[i] == { ||
str[i] == ( || str[i] == <)
{
stack.push(str[i]);
}
/*如果是对称的符号,则从栈中弹出*/
if(str[i] == ] || str[i] == } ||
str[i] == ) || str[i] == >)
{
/*如果栈中没有对象,则说明不平衡*/
if(stack.isempty())
{
cout < "the string is Unblanced" < endl;
return false;
}
/*采用switch-case语句判断*/
switch(str[i])
{
case ]:
{
/*判断是否是匹配的*/
if([ != stack.pop())
{
cout < "Can not blanced with ]" < endl;
return false;
}
break;
}
case ):
{
if(( != stack.pop())
{
cout < "Can not blanced with )" < endl;
return false;
}
break;
}
case }:
{
if({ != stack.pop())
{
cout < "Can not blanced with }" < endl;
return false;
}
break;
}
case >:
{
if(< != stack.pop())
{
cout < "Can not blanced with >" < endl;
return false;
}
break;
}
/*一般的非对称字符*/
default:
break;
}
}
}
/************************************************
*当所有对象遍历完成以后,需要判断栈中是否存在对象
*栈中为空说明是平衡的,非空则说明是非空的对象
************************************************/
if(stack.isempty())
{
cout < "string is blanced!!" < endl;
return true;
}
else/*没有正确的匹配,并输出具体不匹配的符号*/
{
cout < stack.pop() < " " < "Unblance string!!" < endl;
return false;
}
}

采用上面的代码能够符号是否平衡的判断。

接下来说明一下表达式的求值问题,表达式的求值问题主要设计到操作符的优先级问题,比如()、*/、+-这几种符号的优先级是不一样的,其中括号的优先级最好,乘除其次,加减最低,我们通常看到的表达式都是中缀表达式,也就是在操作符的两边都有对象,当然括号除外啦,这种中缀表达式是不便于在程序中处理的,因为存在很多的优先级差别,很难把握从那个位置先计算。

如果在表达式中没有了优先级的问题,求值问题也就变得相对来说更加简单了,后缀表达式是一种非优先级的表达式表示方式,但是如何实现中缀表达式到后缀表达式的切换也是很难实现的。

中缀表达式到后缀表达式的实现如下:

Copyright © 2017-2020 微波EDA网 版权所有

网站地图

Top