数据结构实验：堆栈

Question

要求：
1．实现堆栈的抽象数据类型：实现所有方法，（顺序栈与链栈任选）
以下两个题目任选：
2．实现中缀表达式的算法
3．利用所实现的堆栈实现括号匹配算法：
有三种括号：{}[]()
例：{a+[b*(c+d)]/f}*h 匹配

Answer 1

给你把第三题写了 调试过了 没有问题 第二题的算法先告诉你下吧
设置2个栈 OPND OPTR 一个存放操作数 一个存放运算符 先把一个标记符号推入运算符栈底 然后从输入读入字符
1.如果是操作数 则入OPND栈
2.如果是运算符
（1）运算符优先级高于OPTR栈顶元素 则入栈
（2）运算符优先级低于OPTR栈顶元素 则栈顶元素出栈高优先级运算符入栈 并退出2个OPND栈中的元素 将2个元素进行高优先级的操作 并把结果推入栈OPND
（3）如果读入的是) 栈顶元素是( 则（出栈
（4）如果读入的是标志符 并且运算符栈顶元素也是标记 则结束
因为这个算法的实现工作量相当大 要写优先级判断函数 就没有做了 下面是第三题
#include <stdio.h>
#include <malloc.h>

typedef int Elemtype;

typedef struct StackNode{
Elemtype data;
StackNode* next;
}*LinkStack;

bool InitStack(LinkStack &Top)
{
Top = NULL; //创建一个链栈
return 1;
}

bool Push(LinkStack &Top,Elemtype e)
{
LinkStack p = (StackNode *)malloc(sizeof(StackNode)); //为新节点开辟一个动态存储空间
if(!p)return 0; //如果空间不足 返回false
p->data = e;
p->next = Top; //将元素压入栈顶
Top = p;
return 1;
}

bool IsEmpty(LinkStack Top)
{
return (Top == NULL); //若栈为空 返回ture否则返回false
}

bool Pop(LinkStack &Top,Elemtype &e)
{
LinkStack p = Top;
if(IsEmpty(Top))return 0; //如果栈为空 返回false
e = p->data;
Top = Top->next; //修改栈顶指针 向下指
free(p); //释放栈顶节点空间
return 1;
}

int main()
{
Elemtype c,e;
LinkStack S;
int mark = 1;
InitStack(S);
printf("请输入一个带括号的表达式(按回车结束):");
while ((c = getchar()) != '\n')
{
if (c == '(' || c == '[' || c =='{')Push(S,c);
else if (c == ')')
{
if (IsEmpty(S))mark = 0;
else
{
Pop(S,e);
if (e != '(')mark = 0;
}
}
else if (c == ']')
{
if (IsEmpty(S))mark = 0;
else
{
Pop(S,e);
if (e != '[')mark = 0;
}
}
else if (c == '}')
{
if (IsEmpty(S))mark = 0;
else
{
Pop(S,e);
if (e != '{')mark = 0;
}
}
}
if (IsEmpty(S) && mark == 1)printf("括号匹配!\n");
else printf("括号不匹配!\n");
return 0;
}

Answer 2

//Com.h
#define OK 1
#define ERROR 0
#define OVERFLOW 0
#define Status int
#define ElemType int
#define TRUE 1
#define FALSE 0
#define SElemType char

//SqStack.h

#include "Com.h"
#include <stdlib.h>
#include <malloc.h>

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

typedef struct
{
SElemType *base;
SElemType *top;
ElemType stacksize;
}SqStack;

Status Initstack(SqStack &L)//建栈
{
L.base=(SElemType*)malloc(sizeof(ElemType)*STACK_INIT_SIZE);
if(!L.base)
exit(OVERFLOW);
L.top=L.base;
L.stacksize = STACK_INIT_SIZE;
return OK;
}

Status Gettop(SqStack L,SElemType &e)// 取栈顶元素
{
if(L.top==L.base)
return ERROR;
e = *(L.top-1);
return OK;
}

Status Push(SqStack &L,SElemType &e)//添加元素
{
if(L.top - L.base==STACK_INIT_SIZE)
{
L.base = (SElemType*)realloc(L.base,(L.stacksize+STACKINCREMENT)*sizeof(ElemType));
if(!L.base)
exit(OVERFLOW);
L.top = L.base + L.stacksize;
L.stacksize += STACKINCREMENT;

}
*L.top++ = e;
return OK;
}

Status Pop(SqStack &L, SElemType &e)//弹出元素
{
if(L.top == L.base)
return ERROR;
e = *(--L.top);
return OK;
}

Status DestroyStack(SqStack &L)//销毁栈
{
L.top = L.base;
return OK;
}

Status ClearStack(SqStack &L)
{
if(L.top == L.base)
printf("All Done!");
*L.base++ = NULL;
return OK;
}

Status StackEmpty(SqStack &L)
{
if(L.top == L.base)
return TRUE;
else
return FALSE;
}

Status StackLength(SqStack &L)
{
return (L.top-L.base);
}

//match-stack.cpp
#include "stdafx.h"
#include "SqStack.h"
#include <stdio.h>
#define ARRAYSIZE 20

int main()
{
char arr[ARRAYSIZE];
printf("Input your shizi:");
scanf("%s",arr);
SqStack S;
Initstack(S);
int i ;
for(i = 0;i < ARRAYSIZE; i++)
{
if(arr[i] == '(' || arr[i] == '['||arr[i] =='{')
Push(S,arr[i]);
else if(arr[i] == ')' || arr[i] == ']'||arr[i] == '}')
{
if(S.top == S.base)
{
printf("Input error!");
exit(0);
}
else
Pop(S,*(S.top-1));
}
}

if(StackEmpty(S))
printf("Match!");
else
printf("Not Match!");

return 0;
}本回答被网友采纳

Answer 3

3.给个思路吧：
将字符一个一个放入堆栈，如果遇上),则做出栈操作，直到（；然后如此类推进行；遇到)]}都进行出栈计算的操作；直到遇到另外一般为止。由于好久没有看数据结构了。只有给你一个大致的方法