栈---实现顺序栈及简单的括号匹配问题
程序员文章站
2024-01-24 23:28:34
...
栈
通常情况下,栈(Stack)可定义为只允许在表的末端进行插入和删除的线性表。允许插入和删除的一端称作栈顶(top),不允许插入和删除的一端称作栈底(bottom)。当栈中没有任何元素时则成为空栈。
栈的分类
栈的抽象数据类型有两种典型的存储方式:
- 顺序栈:基于数组的存储表示
- 链式栈:基于链表的存储表达方式
代码实现
//顺序栈的实现
#include<stdlib.h>
#include<iostream>
#include<assert.h>
using namespace std;
const int stackIncreament = 20;//扩容大小
template<class T>
class Stack
{
public:
//构造函数
Stack(int sz = 50)
{
top = -1;
maxSize = sz;
elements = new T[maxSize];
assert(elements != NULL);
}
~Stack() //析构函数
{
delete[]elements;
}
void push(const T& x); //压栈操作
bool pop(T& x); //出栈操作
bool getTop(T& x) //取栈顶元素
{
if (IsEmpty() == true)
return false;
x = elements[top];
return true;
}
//判空
bool IsEmpty()const
{
return (top == -1) ? true : false;
}
//判满
bool IsFull()const
{
return (top == maxSize - 1) ? true : false;
}
//返回栈中元素个数
int getSize()const
{
return top + 1;
}
//将栈置空
void makeEmpty()
{
top = -1;
}
private:
T *elements; //存放栈中元素的栈数组
int top; //栈顶指针
int maxSize; //栈最大可容纳元素个数
void overFloeProcess(); //栈的溢出处理
};
//私有函数,扩充栈的存储空间
template<class T>
void Stack<T>::overFloeProcess()
{
T * newArray = new T[maxSize + stackIncreament];
if (newArray == NULL)
{
cerr << "内存分配失败!" << endl;
exit(1);
}
for (int i = 0; i <= top; i++)
{
newArray[i] = elements[i];
}
maxSize += stackIncreament;
delete[]elements;
}
//压栈操作
template<class T>
void Stack<T>::push(const T& x)
{
while (IsFull() == true){
overFloeProcess();
}
elements[++top] = x;
}
//出栈操作
template<class T>
bool Stack<T>::pop(T& x)
{
if (IsEmpty() == true)
return false;
x = elements[top--];//返回栈顶元素值
return true;
}
//括号匹配
void PrintMatchedPairs(char * exprssion, int size)
{
if (exprssion == NULL)
return;
Stack<int> s(size);
int x;//pop返回的值
int n;//栈中元素的个数
for (int i = 1; i <= size; i++)
{
if (exprssion[i-1] == '(')
s.push(i);
else if (exprssion[i-1] == ')')
{
if (s.pop(x) == true)
cout << x << " 与 " << i << "匹配" << endl;
else
cout << "没有与第" << i << "个右括号匹配的左括号!" << endl;
}
}
while (s.IsEmpty() == false)
{
s.pop(x);
cout << "没有与第" << x << "个右括号匹配的左括号!" << endl;
}
}
int main()
{
char * c = "(0)ii(ooio(o)))";
cout << strlen(c) << endl;
PrintMatchedPairs(c, strlen(c));
return 0;
}
栈的灵活运用之括号配对
在一个字符串”(a * (b + c) - d)”中,位置1的左括号与位置8的右括号匹配,位置4的左括号和位置11的右括号匹配。
在字符串”(a + b)(“中,位置6的左括号没有右括号与之匹配。
利用栈的知识,我们就能轻松地找到已经匹配的左右括号和还未匹配的左右括号。
思路分析
循环遍历字符串,遇到’(‘将位置信息push
,遇到’)’将栈顶的数据pop
,由于栈的先进后出规则,pop
操作得到的信息是与之匹配的左括号的位置。
首先遇到右括号,pop
会返回false,接收false并进行处理。
字符串读完后栈不为空,依次出栈并显示信息,直到栈为空。
//括号匹配
void PrintMatchedPairs(char * exprssion, int size)
{
if (exprssion == NULL)
return;
Stack<int> s(size);
int x;//pop返回的值
int n;//栈中元素的个数
for (int i = 1; i <= size; i++)
{
if (exprssion[i-1] == '(')
s.push(i);
else if (exprssion[i-1] == ')')
{
if (s.pop(x) == true)
cout << x << " 与 " << i << "匹配" << endl;
else
cout << "没有与第" << i << "个右括号匹配的左括号!" << endl;
}
}
while (s.IsEmpty() == false)
{
s.pop(x);
cout << "没有与第" << x << "个右括号匹配的左括号!" << endl;
}
}
上一篇: 栈及栈运用之括号匹配