设计一个判别表达式中左、右括号是否配对出现的算法,采用什么数据结构最佳。
答案:3 悬赏:70 手机版
解决时间 2021-12-03 08:54
- 提问者网友:沦陷
- 2021-12-02 18:47
设计一个判别表达式中左、右括号是否配对出现的算法,采用什么数据结构最佳。
最佳答案
- 五星知识达人网友:拜訪者
- 2021-12-02 19:00
使用“栈” 这种数据结构。
栈 (Stack)是一种后进先出(last in first off,LIFO)的数据结构。
算法基本思想:依次判断表达式中的每个字符,若是左括号就入栈,如果是右括号则出栈,出栈的时候判断是否为空,如果为空,则说明不匹对,最后读到表达式末尾没有字符了,再判断一下栈是否为空,如果为空,则说明匹配,不为空,说明不匹配。
参考如下代码,引用地址(http://blog.csdn.net/kkkkkxiaofei/article/details/8293980)
#include
#include //malloc,realloc
#include //含有overflow
#include //exit()
#define S_SIZE 100 //栈的空间大小
#define STACKINCREAMENT 10//增加空间
struct SqStack{
int *base; //栈底
int *top; //栈顶
int stacksize; //栈当前的存储空间
};
void main()
{//子函数声明
void InitStack(SqStack &S);//初始化空栈
int StackEmpty(SqStack S);//判空
void push(SqStack &S,int e);//进栈
void pop(SqStack &S,int &e);//出栈
//主函数开始
SqStack s;//初始化空栈
InitStack(s);
char ch[100],*p;int e;
p=ch;
printf("输一个含义有()[]{}的括号表达式:
");
gets(ch);
while(*p)
{
switch (*p)
{
case '{':
case '[':
case '(': push(s,*p++);break;//只要是左括号就入栈
case '}':
case ']':
case ')':pop(s,e);
if ((e=='{' && *p=='}') ||(e=='[' && *p==']') || (e=='(' && *p==')'))
p++;
else
{printf("括号不匹配!");exit(OVERFLOW);}
break;
default :p++;//其他字符就后移
}
}
if (StackEmpty(s))
printf("括号匹配成功");
else
printf("缺少右括号!");
printf("
");
}
void InitStack(SqStack &S)
{S.base=(int *)malloc(S_SIZE*sizeof(int));
S.stacksize=S_SIZE;
S.top=S.base;//初始化空栈
}
int StackEmpty(SqStack S)
{
if(S.base==S.top)
return 1;
else
return 0;
}
void push(SqStack &S,int e)
{//进栈
if(S.top-S.base>=S.stacksize)
{S.base=(int *)realloc(S.base,(S.stacksize+STACKINCREAMENT)*sizeof(int));
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREAMENT;}
*(S.top)=e;
S.top++;
}
void pop(SqStack &S,int &e)
{//出栈
if(S.base!=S.top)
{S.top--;
e=*S.top;}
}
栈 (Stack)是一种后进先出(last in first off,LIFO)的数据结构。
算法基本思想:依次判断表达式中的每个字符,若是左括号就入栈,如果是右括号则出栈,出栈的时候判断是否为空,如果为空,则说明不匹对,最后读到表达式末尾没有字符了,再判断一下栈是否为空,如果为空,则说明匹配,不为空,说明不匹配。
参考如下代码,引用地址(http://blog.csdn.net/kkkkkxiaofei/article/details/8293980)
#include
#include
#include
#include
#define S_SIZE 100 //栈的空间大小
#define STACKINCREAMENT 10//增加空间
struct SqStack{
int *base; //栈底
int *top; //栈顶
int stacksize; //栈当前的存储空间
};
void main()
{//子函数声明
void InitStack(SqStack &S);//初始化空栈
int StackEmpty(SqStack S);//判空
void push(SqStack &S,int e);//进栈
void pop(SqStack &S,int &e);//出栈
//主函数开始
SqStack s;//初始化空栈
InitStack(s);
char ch[100],*p;int e;
p=ch;
printf("输一个含义有()[]{}的括号表达式:
");
gets(ch);
while(*p)
{
switch (*p)
{
case '{':
case '[':
case '(': push(s,*p++);break;//只要是左括号就入栈
case '}':
case ']':
case ')':pop(s,e);
if ((e=='{' && *p=='}') ||(e=='[' && *p==']') || (e=='(' && *p==')'))
p++;
else
{printf("括号不匹配!");exit(OVERFLOW);}
break;
default :p++;//其他字符就后移
}
}
if (StackEmpty(s))
printf("括号匹配成功");
else
printf("缺少右括号!");
printf("
");
}
void InitStack(SqStack &S)
{S.base=(int *)malloc(S_SIZE*sizeof(int));
S.stacksize=S_SIZE;
S.top=S.base;//初始化空栈
}
int StackEmpty(SqStack S)
{
if(S.base==S.top)
return 1;
else
return 0;
}
void push(SqStack &S,int e)
{//进栈
if(S.top-S.base>=S.stacksize)
{S.base=(int *)realloc(S.base,(S.stacksize+STACKINCREAMENT)*sizeof(int));
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREAMENT;}
*(S.top)=e;
S.top++;
}
void pop(SqStack &S,int &e)
{//出栈
if(S.base!=S.top)
{S.top--;
e=*S.top;}
}
全部回答
- 1楼网友:人類模型
- 2021-12-02 20:07
很明显,用栈
如果是左括号,入栈
如果是右括号,看栈顶是不是左括号,如果是就把那个左括号出栈;否则不配对(可以直接结束算法)
处理完所有符号后,栈为空则配对成功,否则不配对
如果是左括号,入栈
如果是右括号,看栈顶是不是左括号,如果是就把那个左括号出栈;否则不配对(可以直接结束算法)
处理完所有符号后,栈为空则配对成功,否则不配对
- 2楼网友:行路难
- 2021-12-02 19:11
当然用栈这个数据结构,设置两个栈,我有相关实现的代码给你参考一下
//栈数据结构的实现MyStack.h
#ifndef MYSTACK_H
#define MYSTACK_H
template
class MyStack
{
public:
MyStack(int _size);
~MyStack();
bool StackEmpty();
bool StackFull();
void ClearStack();
int StackLength();
void StackTraverse();
bool push(T& _element);
T& pop();
private:
T* m_pBuffer; //栈的内存空间的地址
int m_iCapacity; // 栈的容量
int m_iTop; //栈顶位置,栈底位置是确定的
};
#endif
-------------------------------------------
MyStack.cpp 模板类的声明和实现在使用的时候不能分开,可以把声明和实现放在一个文件中,也可以在主文件中包含实现的文件
#include "MyStack.h"
template
MyStack
{
this->m_iCapacity =_size;
this->m_pBuffer =new T[_size];
this->m_iTop=0;
}
template
MyStack
{
delete[] this->m_pBuffer;
this->m_pBuffer =NULL;
}
template
bool MyStack
{
return this->m_iTop ==0?true:false;
}
template
bool MyStack
{
return this->m_iCapacity == this->m_iTop?true:false;
}
template
void MyStack
{
this->m_iTop =0;
}
template
int MyStack
{
return this->m_iTop;
}
template
bool MyStack
{
try
{
if (this->StackFull())
{
throw string("Stack Overflow");
}
else
{
this->m_pBuffer[this->m_iTop] =_element;
this->m_iTop++;
return true;
}
}
catch(string& str) // 有未处理的异常错误是这里的函数参数不应该是string类型的指针,很显然啊,抛出的是一个字符串常量 。一开始用默认填充的string* 总是出错
{
cout<
}
template
T& MyStack
{
try
{
if (this->StackEmpty())
{
throw string(" Stack Empty"); //哪里出现异常,就在哪里捕获,不应该在外部进行异常捕获,否则不易定位到异常的地点
}
else
{
this->m_iTop--;
return this->m_pBuffer[this->m_iTop];
}
}
catch(string& str)
{
cout<
}
template
void MyStack
{
for (int i =this->m_iTop-1; i>=0; i--)
{
cout<
}
}
--------------------------------------------------------
main.cpp 测试部分
#include
#include "MyStack.cpp"
#include "Customer.h"
int main()
{
MyStack
ps->push(Customer("Selina",22));
ps->push(Customer("Johnaon",54));
ps->push(Customer("Richard",38));
ps->push(Customer("Alice",18));
ps->push(Customer("Elizabeth",89));
ps->StackTraverse();
cout<<"-------------------"<
cout<<"-------------------"<
cout<<"-------------------"<
delete ps;
ps=NULL;
system("pause");
return 0;
}
---利用上面实现的栈结构,完成表达式括号的匹配任务
栈:实现判断字符串中的括号是否匹配,要考虑的情况还挺多的
#include
#include "MyStack.cpp"
int main()
{
char str[] ="{[]}"; //strlen()函数的参数是char* 类型,这里不能使用string定义一个字符串常量
char currentNeed =0; //当前栈顶需要匹配的字符串
MyStack
MyStack
for (int i=0; i
if (str[i] != currentNeed)
{
ps1->push(str[i]);
switch(str[i])
{
case '{':
if (currentNeed !=0)
{
ps2->push(currentNeed);
}
currentNeed ='}';
break;
case '[':
if (currentNeed !=0)
{
ps2->push(currentNeed);
}
currentNeed =']';
break;
case '(':
if (currentNeed !=0)
{
ps2->push(currentNeed);
}
currentNeed =')';
break;
default: //如果最后还剩一个不是上面三种字符的情况,字符串括号的匹配肯定是不成功的,这时候可以直接判断不成功
cout<<"字符串中的括号不匹配"<
return 0;
}
}
else
{
//匹配成功两个栈的栈顶都弹出,为了后面的判断
ps1->pop();
currentNeed =ps2->pop(); //上一次匹配成功之后,进入下一次匹配的时候首先要保证匹配永远都是和被匹配栈的栈顶匹配
//如果被匹配ps2的栈以完全出栈,这时候匹配的栈ps1还有值,这时候字符串的括号肯定是不匹配的,所以在执行最后一次循环的之前把当前匹配的字符设定为0
// 这里有点缺陷,由于我的pop()方法在栈空的时候是报错的,无法再重置currentNeed的值,得到的是一个非法的值,执行结果正确,有瑕疵
}
}
if (ps1->StackEmpty())
{
cout<<"字符串中的括号匹配成功"<
else{
cout<<"字符串中的括号不匹配"<
system("pause");
return 0;
}
我要举报
如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息,可以点下面链接进行举报!
点此我要举报以上问答信息
大家都在看
推荐资讯