关于数据结构与算法中栈的问题求解，但是不要用stl容器来做，尽量自己定义一个栈
链表实现栈的功能即可。参考如下
#include <iostream>
#include <string>
#define ERROR 0
#define OK 1
#define OVERFLOW 0
typedef int Status;
using namespace std;
typedef struct stack
{
char* base;
char* top;
int stacksize;
}SqStack;
class solution
{
public:
int isvalid(string s)
{
if (s.length() % 2 != 0) //先判断字符串长度
return 0;
init_stack(S,s); //初始化栈--仅仅是申请空间
for(unsigned int i=0;i<s.length();i++)
{
if(s[i]=='(' || s[i]=='[' || s[i]=='{') //如果是左括号，入栈
push_stack(S,s[i]);
else
{//如果是右括号，出栈
char t=0;
if(pop_stack(S,t))
{
if( (s[i]==')' && t=='(') || (s[i]==']' && t=='[') || (s[i]=='}' && t=='{') )
continue;
else
return 0;
}else
return 0;
}
}
return empty_stack(S);
}
Status init_stack(SqStack& S,string s)
{
S.base = new char[s.length()+1];
if (!S.base) return(OVERFLOW);
S.top = S.base;
S.stacksize = s.length()+1;
return OK;
}
Status push_stack(SqStack& S,char e)
{
if (S.top-S.base==S.stacksize) return ERROR;
*S.top = e;
S.top++;
return OK;
}
Status pop_stack(SqStack& S, char& e)
{
if (S.base == S.top) return ERROR;
--S.top;
e = *S.top;
return OK;
}
Status empty_stack(SqStack S)
{
if (S.top == S.base)
return true;
return false;
}
private:
//string s;
SqStack S;
};
int main()
{
string s;
cin >> s;
solution a;
if(a.isvalid(s))
cout <<"true";
else
cout <<"false";
return 0;
}
没那么麻烦，甚至都不要堆栈
只要一个整数
初始为0，遇到( +1，遇到) -1，如果中途有负数或者结果不为0就是无效的。否则就是有效。
【以下回答由 GPT 生成】
首先，我们可以使用一个自定义的栈数据结构来实现有效的括号匹配问题。
我们需要定义一个栈数据结构，它必须具备以下几个功能： - 入栈操作（push）：将元素压入栈顶 - 出栈操作（pop）：将栈顶元素弹出 - 获取栈顶元素（top）：返回栈顶元素但不移除 - 判断栈是否为空（isEmpty）：如果栈为空则返回True，否则返回False
以下是一个基于数组的简单栈的实现：
class Stack {
private:
int topIndex;
int* arr;
int maxSize;
public:
Stack(int size) {
topIndex = -1;
maxSize = size;
arr = new int[size];
}
~Stack() {
delete[] arr;
}
void push(int num) {
if (topIndex >= maxSize - 1) {
cout << "Stack overflow" << endl;
return;
}
arr[++topIndex] = num;
}
void pop() {
if (topIndex < 0) {
cout << "Stack underflow" << endl;
return;
}
--topIndex;
}
int top() {
if (topIndex < 0) {
cout << "Stack is empty" << endl;
throw "Stack is empty";
}
return arr[topIndex];
}
bool isEmpty() {
return topIndex == -1;
}
};
接下来，我们可以使用定义的栈数据结构来实现括号匹配算法。
算法思路如下： - 创建一个空栈 - 遍历输入字符串的每一个字符 - 如果是左括号（‘(’, ‘[’, ‘{’），则将其压入栈中 - 如果是右括号（‘)’, ‘]’, ‘}’），则判断栈顶元素是否对应的左括号 - 如果栈为空或栈顶元素不是对应的左括号，则括号不匹配，返回False - 如果栈顶元素是对应的左括号，则将栈顶元素弹出 - 如果遍历结束后，栈为空，则括号匹配，返回True；否则，括号不匹配，返回False
以下是用C++实现括号匹配算法的代码：
bool isValidParentheses(string s) {
Stack stack(s.length());
for (int i = 0; i < s.length(); i++) {
char c = s[i];
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
} else if (c == ')' || c == ']' || c == '}') {
if (stack.isEmpty()) {
return false; // 括号不匹配
}
char topChar = stack.top();
if ((c == ')' && topChar != '(') ||
(c == ']' && topChar != '[') ||
(c == '}' && topChar != '{')) {
return false; // 括号不匹配
}
stack.pop();
}
}
// 遍历结束后栈为空则括号匹配，否则括号不匹配
return stack.isEmpty();
}
int main() {
string s1 = "([{}])"; // 括号匹配，返回True
string s2 = "(]"; // 括号不匹配，返回False
string s3 = "([)]"; // 括号不匹配，返回False
string s4 = "()[]{}"; // 括号匹配，返回True
string s5 = "((("; // 括号不匹配，返回False
cout << isValidParentheses(s1) << endl;
cout << isValidParentheses(s2) << endl;
cout << isValidParentheses(s3) << endl;
cout << isValidParentheses(s4) << endl;
cout << isValidParentheses(s5) << endl;
return 0;
}
这样，我们就完成了用C++实现有效的括号匹配算法的过程。
【相关推荐】