注册 登录
编程论坛 数据结构与算法

求助程序哪里有问题?括号匹配问题

龙岩花界 发布于 2018-10-18 14:18, 2195 次点击
括号配对
#include<stdio.h>
#include<iostream.h>
#include<stdlib.h>
#include<string.h>
typedef char ElemType;
#define true 1
#define false 0
#define MaxSize 10
typedef struct
{
    ElemType data[MaxSize];
    int top;
}StType;
void InitStack(StType *&s)
{
    s=(StType *)malloc(sizeof(StType));
    s->top=-1;
}
void DestoryStack(StType *&s)
{
    free(s);
}
bool StackEmpty(StType *&s)
{
    return(s->top==-1);
}
bool Push(StType *&s,ElemType e)
{   if(s->top==MaxSize)
       return 0;
s->top++;
s->data[s->top]=e;
return 1;
}
bool Pop(StType *&s,ElemType &e)
{   if(s->top==-1)
       return 0;
e=s->data[s->top];
s->top--;
return true;
}
bool GetTop(StType *&s,ElemType &e)
{   if(s->top==-1)
       return false;
e=s->data[s->top];
return true;
}

bool Match(char exp[],int n)
{
    int i=0;char e;
    bool match=true;
    StType * st;
    InitStack (st);
    while(i<n&&match)
    {   if(exp[i]=='(')
        Push  (st,exp[i]);
     else if(exp[i]==')')
     { if(GetTop(st,e)==true)
        {
         if(e!='(')
        match=false;
     else
         Pop(st,e);
     }
     else match=false;
     }
     i++;
    }
    if(!StackEmpty(st))
        match=false;
    DestoryStack(st);
    return match;
}
int main()
{
char exp[20];
printf("请输入表达式:\n");
gets(exp);
if(Match(exp,strlen(exp)==1))
printf("表达式%s 括号配对\n",exp);
else
printf("表达式%s 括号不配对\n",exp);
return 0;
}
7 回复
#2
MeandC2018-10-19 16:03
感觉你定义的栈有问题,你看下后面的代码。
读取到左括号就进栈,读取到右括号就将栈里的元素出栈进行匹配,如果左右括号不是同类型或者最后栈不为空就说明左右括号不匹配。
typedef struct
{
    char *base;
    char *top;
    int stacksize;
}StType;
void InitStack(StType &s)
{
    s.base=(char *)malloc(sizeof(char)*MaxSize);
    s.top=s.base;
    s.stacksize=MaxSize;
}

#3
龙岩花界2018-10-19 19:30
定义的栈应该不存在问题吧
#4
龙岩花界2018-10-19 19:33
你这边可以对我的代码进行修改,发一个完整的过来吗?
#5
林月儿2018-10-19 22:01
程序代码:
#include <iostream>
#include <vector>
using namespace std;

 
int main()
{
    string str;
    vector<char> vec;
    cout<<"请输入表达式:";
    cin>>str;
    for(string::iterator it = str.begin(); it != str.end(); it++)
    {
        if(*it=='(')
            vec.push_back('(');
        else if(*it==')'){
            if(vec[vec.size()-1]=='(')
                vec.pop_back();
            else
                vec.push_back(')');
        }
    }
    string res = vec.size()==0?"":"";
    cout<<"表达式"<<str<<"括号"<<res<<"配对"<<endl;
    return 0;
}
#6
MeandC2018-10-20 18:53
回复 4楼 龙岩花界
okok
我用visual studio 2017写了一段代码,给你参考,如果你用的不是vs ,就把gets_s 改成gets就好了
程序代码:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

//函数结果状态码
#define ok 1
#define error 0
#define overflow -2
typedef struct {//定义栈
    char *base;
    char *top;
    int stacksize;
}stack;
typedef int status;//status是函数的类型,值为结果状态代码
status push(stack &s, char e) {//进栈
    if (s.top - s.base == s.stacksize) {//栈满,追加空间
        s.base = (char*)realloc(s.base, (s.stacksize + 20) * sizeof(char));
        if (!s.base)exit(overflow);
        s.top = s.base + s.stacksize;
        s.stacksize += 20;
    }
    *s.top++ = e;
    return ok;
}
status pop(stack &s, char &e) {//出栈
    if (s.top == s.base) return error;
    e = *--s.top;
    return ok;
}
status initstack(stack &s) {//栈初始化
    s.base = (char*)malloc(sizeof(char) * 100);
    if (!s.base)exit(overflow);//存储分配失败
    s.top = s.base;
    s.stacksize = 100;
    return ok;
}
int main(void) {
    stack s;
    initstack(s);//初始化栈

    char ch[300];
    printf("请输入一个表达式:");
    gets_s(ch);

    char *p =ch;  //申请字符指针变量并指向字符数组首地址   
    char c;
    int a=1;//a的值为0或1,当单个括号成功时为1,当单个括号不成功时值为0

    while (a && *p!='\0')//当括号匹配成功并且还有字符是继续循环
    {
        if (*p == '(' || *p == '[' || *p == '{')
            push(s, *p);
         else if (*p == ')' || *p == ']' || *p == '}') {
            switch (*p) {
            case ')':pop(s, c);
                if (c == '(') a = 1;
                else a = 0;
                break;
            case ']':pop(s, c);
                if (c == '[')a = 1;
                else a = 0;
                break;
            case '}':pop(s, c);
                if (c == '{')a = 1;
                else a = 0;
                break;
            }
         }
        p++;
    }
    if (s.top == s.base && a != 0)printf("括号匹配\n");//栈为空说明左右括号个数相等,a!=0则说明最后一个配对时是同类型的括号
    else printf("括号不匹配\n");
   
    system("pause");//暂停
    return 0;
}
#7
龙岩花界2018-10-21 15:54
谢谢大佬,但是我运行之后发现你的程序跟我的程序有一样的问题,就是有些配对是对的,但是有些又是错的,我感觉程序应该还是有小问题。还没找出来。
#8
林月儿2018-10-21 16:33
栈顶元素没判断吧  
 while (a && *p!='\0')//当括号匹配成功并且还有字符是继续循环
    {
        if (*p == '(' || *p == '[' || *p == '{')
            push(s, *p);
         else if (*p == ')' || *p == ']' || *p == '}') {
            switch (*p) {
            case ')':pop(s, c);
                if (c == '(') a = 1;
                else a = 0;
                break;
            case ']':pop(s, c);
                if (c == '[')a = 1;
                else a = 0;
                break;
            case '}':pop(s, c);
1