设计一个判别表达式中左、右括号是否配对出现的算法，采用什么数据结构最佳。 设计一个判别表达式中左、右括号是否配对出现的算法，采用（）数...
使用“栈” 这种数据结构。
栈 (Stack)是一种后进先出(last in first off，LIFO)的数据结构。
算法基本思想：依次判断表达式中的每个字符，若是左括号就入栈，如果是右括号则出栈，出栈的时候判断是否为空，如果为空，则说明不匹对，最后读到表达式末尾没有字符了，再判断一下栈是否为空，如果为空，则说明匹配，不为空，说明不匹配。
参考如下代码，引用地址（http://blog.csdn.net/kkkkkxiaofei/article/details/8293980）
#include <stdio.h>
#include <malloc.h> //malloc,realloc
#include <math.h> //含有overflow
#include <process.h> //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;}
}
当然用栈这个数据结构，设置两个栈，我有相关实现的代码给你参考一下
//栈数据结构的实现
MyStack.h
#ifndef MYSTACK_H
#define MYSTACK_H
template<typename T>
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<typename T> //模板类的成员函数的写法要完整，指定模板参数
MyStack<T>::MyStack(int _size)
{
this->m_iCapacity =_size;
this->m_pBuffer =new T[_size];
this->m_iTop=0;
}
template<typename T>
MyStack<T>::~MyStack()
{
delete[] this->m_pBuffer;
this->m_pBuffer =NULL;
}
template<typename T>
bool MyStack<T>::StackEmpty()
{
return this->m_iTop ==0?true:false;
}
template<typename T>
bool MyStack<T>::StackFull()
{
return this->m_iCapacity == this->m_iTop?true:false;
}
template<typename T>
void MyStack<T>::ClearStack()
{
this->m_iTop =0;
}
template<typename T>
int MyStack<T>::StackLength()
{
return this->m_iTop;
}
template<typename T>
bool MyStack<T>::push(T& _element)
{
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<<str<<endl;
}
}
template<typename T> // 最有意义的一部分，更改了弹出栈的实现，以函数参数的方式实在太不人性化了
T& MyStack<T>::pop()
{
try
{
if (this->StackEmpty())
{
throw string(" Stack Empty"); //哪里出现异常，就在哪里捕获，不应该在外部进行异常捕获，否则不易定位到异常的地点
}
else
{
this->m_iTop--;
return this->m_pBuffer[this->m_iTop];
}
}
catch(string& str)
{
cout<<str<<endl;
}
}
template<typename T>
void MyStack<T>::StackTraverse()
{
for (int i =this->m_iTop-1; i>=0; i--)
{
cout<<this->m_pBuffer[i]; //如果是自定义的类型需要重载<<操作符
}
}
--------------------------------------------------------
main.cpp 测试部分
#include <stdlib.h>
#include "MyStack.cpp"
#include "Customer.h"
int main()
{
MyStack<Customer>* ps =new MyStack<Customer>(5);
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<<"-------------------"<<endl;
ps->push(Customer("Stephen",67));
cout<<"-------------------"<<endl;
cout<<ps->pop(); //异常Stack Empty，不能够在回调printInfo()函数了，否则会出现另一个异常
cout<<"-------------------"<<endl;
ps->StackTraverse(); //弹出的元素已不在
delete ps;
ps=NULL;
system("pause");
return 0;
}
---利用上面实现的栈结构，完成表达式括号的匹配任务
栈：实现判断字符串中的括号是否匹配，要考虑的情况还挺多的
#include <stdlib.h>
#include "MyStack.cpp"
int main()
{
char str[] ="{[]}"; //strlen()函数的参数是char* 类型，这里不能使用string定义一个字符串常量
char currentNeed =0; //当前栈顶需要匹配的字符串
MyStack<char>* ps1 =new MyStack<char>(20);
MyStack<char>* ps2 =new MyStack<char>(20);
for (int i=0; i<strlen(str); 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<<"字符串中的括号不匹配"<<endl;
system("pause");
return 0;
}
}
else
{
//匹配成功两个栈的栈顶都弹出，为了后面的判断
ps1->pop();
currentNeed =ps2->pop(); //上一次匹配成功之后，进入下一次匹配的时候首先要保证匹配永远都是和被匹配栈的栈顶匹配
//如果被匹配ps2的栈以完全出栈，这时候匹配的栈ps1还有值，这时候字符串的括号肯定是不匹配的，所以在执行最后一次循环的之前把当前匹配的字符设定为0
/*if (ps2->StackEmpty()")
{
currentNeed =0;
}*/
// 这里有点缺陷，由于我的pop()方法在栈空的时候是报错的，无法再重置currentNeed的值，得到的是一个非法的值，执行结果正确，有瑕疵
}
}
if (ps1->StackEmpty())
{
cout<<"字符串中的括号匹配成功"<<endl;
}
else{
cout<<"字符串中的括号不匹配"<<endl;
}
system("pause");
return 0;
}
很明显，用栈
如果是左括号，入栈
如果是右括号，看栈顶是不是左括号，如果是就把那个左括号出栈；否则不配对（可以直接结束算法）
处理完所有符号后，栈为空则配对成功，否则不配对
~
相关要点总结：
17574373558：用C++编程
吉泉答：include<stdio.h> include<iostream> include<stack> using namespace std;int main(){ bool islegal=true;stack<char> a; //栈 char s[100];gets(s);for(int i=0;s[i];i++){ switch(s[i]){ case '(':case '[':case '{': a.push(s[i]); break; //入栈 case '...
17574373558：在线求大神数据结构c#表达式计算
吉泉答：2.算法：自左至右扫描infixExp，读入每项并分析其对应的语法成分：1)当输入的是操作数，则直接输出到postfixExp中。2)当输入的是左括号，则把它压栈。3)当输入的是右括号，先判断栈是否为空，若为空则括号不匹配；若非空，则把栈中的项依次弹出，直到遇到第1个左括号为止，将弹出的项输出到...
17574373558：用栈实现括号匹配的检验
吉泉答：include <stdio.h> include <string.h> define MAX_STACK 100 struct stStack { char szStack[MAX_STACK];int nTop;};void InitStack(stStack& s){ s.nTop = -1;} char Push(stStack& s, char c){ if (s.nTop == MAX_STACK - 1)return 0;s.nTop ++;s.szStack[s.nTop] = c...
17574373558：试用与非门设计一个判别电路,用以判别8421BCD码所表示的十进制数是否...
吉泉答：8421码就是用4位二进制数表示的数字范围0000~1111. 权位分别为8，4，2，1。例如1111表示十进制数8+4+2+1=15.因此你需要判别大于3，就是判别二进制数是否大于0011.我们假设4个值A,B,C,D来表示这4个位。那么当A=0，B=0，C=0，或A=0，B=0，C=1，D=0时结果只有0000，0001和0010，即...
17574373558：fortran逻辑表达式(x(1).gt.1).or.(x(2).gt.1).or.(x(3).gt.1).or...
吉泉答：逻辑IF语句判别逻辑表达式的值是否为“真”，并执行一操作。其一般形式为：IF(逻辑表达式) 执行语句。如果条件成立（即逻辑表达式值是‘真’），则执行其后紧跟的执行语句，而后执行下一条语句；如果条件不成立，则整个IF语句不作任何操作，只是起下滑作用，使控制转移到IF语句的下一个语句。IF语句最大的...
17574373558：c语言。。||是符号或,优先级是从左到右判断。为什么如果第一个...
吉泉答：这是C语言，以及基本上所有常见的语言的“短路”逻辑，一旦一个表达式判定出肯定为真或者假，就不会继续后面的判断。这种特性很有用，比如你有一个判断：if (A || f(xxx)) { } 其中A为真的可能性非常大，那么f函数的调用次数就减少了，如果f函数是一个比较耗费资源的操作，就会给整个表达式节省...
17574373558：c语言软件题
吉泉答：printf("\n右括号多余!");return;} else { GetTop(&S,&ch);if(Match(ch,str[i])) /*用Match判断两个括号是否匹配*/ Pop(&S,&ch); /*已匹配的左括号出栈*/ else { printf("\n对应的左右括号不同类!");return;} } }/*switch*/ }/*for*/ if(IsEmpty(&S))printf("\n...
17574373558：关于数据结构(C++描述)的3个弱问
吉泉答：1.B 括号匹配的过程，是先让“左括弧”暂存起来，一直等到与之对应的“右括弧”出现，将该对括弧从待匹配序列中删去，称为一次成功匹配。按照此法，依次使得所有括弧匹配完毕。故此，先进入的“左括弧”后得到匹配而后被删，后进入的“左括弧”先得到匹配而先被删除。如此过程，具有很明显的“先进后出...
17574373558：中括号里面的小括号算完了要把中括号转化成小括号吗?
吉泉答：2. 括号的优先级：在数学中，小括号具有最高的优先级，其次是中括号和大括号，最后是尖括号。如果一个表达式中同时包含多种类型的括号，通常先计算小括号里面的内容。3. 括号的配对：在使用括号时，需要注意每个左括号都要与一个右括号配对使用。如果括号没有正确地配对使用，就会导致表达式的含义发生...
17574373558：if语句怎么判断一个字符的类型?
吉泉答：当有多个分支选择时，可采用if-else-if语句，其一般形式为：if(表达式1)语句1;else if(表达式2)语句2;else if(表达式3)语句3;…else if(表达式m)语句m;else 语句n;其语义是：依次判断表达式的值，当出现某个值为真时，则执行其对应的语句。然后跳到整个if语句之外继续执行程序。 如果所有的...