棧的經(jīng)典運(yùn)用
加入技術(shù)交流群
本文采用C++中的vector實(shí)現(xiàn)棧結(jié)構(gòu)，然后利用棧實(shí)現(xiàn)判斷平衡符號(hào)，實(shí)現(xiàn)中綴表達(dá)式到后綴表達(dá)式的轉(zhuǎn)換，并依據(jù)棧實(shí)現(xiàn)簡(jiǎn)單的整數(shù)加減乘除運(yùn)算。
首先棧的實(shí)現(xiàn)，由于在C++中采用了vector來(lái)代替原始的數(shù)組操作，這種比較方便的容器能較好的實(shí)現(xiàn)數(shù)組的功能，當(dāng)然棧也可以采用鏈表實(shí)現(xiàn)，但是我認(rèn)為鏈表沒(méi)有數(shù)組直觀，而且在實(shí)際的計(jì)算機(jī)里也是采用連續(xù)的存儲(chǔ)空間作為?？臻g的，因此選擇Vector。主要實(shí)現(xiàn)三個(gè)操作，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
#endif
實(shí)現(xiàn)了簡(jiǎn)單的棧類，接下來(lái)采用棧實(shí)現(xiàn)一些簡(jiǎn)單的運(yùn)用。
符號(hào)的平衡問(wèn)題
在語(yǔ)言中往往需要判斷一些符號(hào)是否是成對(duì)出現(xiàn)的，比如<>,{},[],()，通常在C++中也只有這幾種對(duì)稱問(wèn)題，如何讓判斷符號(hào)的對(duì)稱也是很多代碼判斷的首要任務(wù)。當(dāng)然實(shí)現(xiàn)的方式是多種多樣的，采用棧的實(shí)現(xiàn)會(huì)相對(duì)更加簡(jiǎn)單?；镜膶?shí)現(xiàn)思路如下：
假設(shè)在讀入一串字符串以后，如果遇到對(duì)稱符號(hào)的左邊部分，則將其壓入棧中，當(dāng)遇到對(duì)稱符號(hào)的右邊部分，則彈出棧中的一個(gè)對(duì)象，實(shí)現(xiàn)比對(duì)，如果是對(duì)稱的，則說(shuō)明當(dāng)前的符號(hào)是平衡的，如果不對(duì)稱，則說(shuō)明當(dāng)前字符串是不平衡的，當(dāng)字符串讀完以后，如果所有的符號(hào)都是平衡的，棧中此時(shí)應(yīng)該就是為空，通過(guò)判斷棧中是否為空，說(shuō)明字符串是否是符號(hào)平衡的。
依據(jù)上面實(shí)現(xiàn)的棧類，實(shí)現(xiàn)符號(hào)平衡判斷的過(guò)程比較簡(jiǎn)單，如下所示：
bool isbalance(const string &str)
{
string::size_type len = str.size();
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]);
}
/*如果是對(duì)稱的符號(hào)，則從棧中彈出*/
if(str[i] == ] || str[i] == } ||
str[i] == ) || str[i] == >)
{
/*如果棧中沒(méi)有對(duì)象，則說(shuō)明不平衡*/
if(stack.isempty())
{
cout << "the string is Unblanced" << endl;
return false;
}
/*采用switch-case語(yǔ)句判斷*/
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;
}
/*一般的非對(duì)稱字符*/
default:
break;
}
}
}
評(píng)論