棧的經典運用
加入技術交流群
本文采用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
#endif
實現了簡單的棧類，接下來采用棧實現一些簡單的運用。
符號的平衡問題
在語言中往往需要判斷一些符號是否是成對出現的，比如<>,{},[],()，通常在C++中也只有這幾種對稱問題，如何讓判斷符號的對稱也是很多代碼判斷的首要任務。當然實現的方式是多種多樣的，采用棧的實現會相對更加簡單。基本的實現思路如下：
假設在讀入一串字符串以后，如果遇到對稱符號的左邊部分，則將其壓入棧中，當遇到對稱符號的右邊部分，則彈出棧中的一個對象，實現比對，如果是對稱的，則說明當前的符號是平衡的，如果不對稱，則說明當前字符串是不平衡的，當字符串讀完以后，如果所有的符號都是平衡的，棧中此時應該就是為空，通過判斷棧中是否為空，說明字符串是否是符號平衡的。
依據上面實現的棧類，實現符號平衡判斷的過程比較簡單，如下所示：
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;
}
}
}
評論