棧的經(jīng)典運(yùn)用
加入技術(shù)交流群
本文采用C++中的vector實(shí)現(xiàn)棧結(jié)構(gòu)，然后利用棧實(shí)現(xiàn)判斷平衡符號，實(shí)現(xiàn)中綴表達(dá)式到后綴表達(dá)式的轉(zhuǎn)換，并依據(jù)棧實(shí)現(xiàn)簡單的整數(shù)加減乘除運(yùn)算。
首先棧的實(shí)現(xiàn)，由于在C++中采用了vector來代替原始的數(shù)組操作，這種比較方便的容器能較好的實(shí)現(xiàn)數(shù)組的功能，當(dāng)然棧也可以采用鏈表實(shí)現(xiàn)，但是我認(rèn)為鏈表沒有數(shù)組直觀，而且在實(shí)際的計(jì)算機(jī)里也是采用連續(xù)的存儲空間作為?？臻g的，因此選擇Vector。主要實(shí)現(xiàn)三個操作，push、pop以及為空判斷?；镜男问饺缦拢?/p>本文引用地址：http://2s4d.com/article/201612/324510.htm
#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)了簡單的棧類，接下來采用棧實(shí)現(xiàn)一些簡單的運(yùn)用。
符號的平衡問題
在語言中往往需要判斷一些符號是否是成對出現(xiàn)的，比如<>,{},[],()，通常在C++中也只有這幾種對稱問題，如何讓判斷符號的對稱也是很多代碼判斷的首要任務(wù)。當(dāng)然實(shí)現(xiàn)的方式是多種多樣的，采用棧的實(shí)現(xiàn)會相對更加簡單。基本的實(shí)現(xiàn)思路如下：
假設(shè)在讀入一串字符串以后，如果遇到對稱符號的左邊部分，則將其壓入棧中，當(dāng)遇到對稱符號的右邊部分，則彈出棧中的一個對象，實(shí)現(xiàn)比對，如果是對稱的，則說明當(dāng)前的符號是平衡的，如果不對稱，則說明當(dāng)前字符串是不平衡的，當(dāng)字符串讀完以后，如果所有的符號都是平衡的，棧中此時應(yīng)該就是為空，通過判斷棧中是否為空，說明字符串是否是符號平衡的。
依據(jù)上面實(shí)現(xiàn)的棧類，實(shí)現(xià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]);
}
/*如果是對稱的符號，則從棧中彈出*/
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;
}
}
}
評論