实验3栈-实验报告

（三）实验代码
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <malloc.h>
typedef char Status;
typedef char SElemType;
typedef int status;
typedef int ElemType;
{//构造一个空栈S
S.base = (SElemType*)malloc(stack_INIT_SIZE * sizeof(SElemType));
if (!S.base)return(ERROR);
S.top = S.base;
S.stacksize = stack_INIT_SIZE;
return OK;
}
printf("%d\n",sum);
return OK;
}
int main()
{
Sqstack S;
iniStack(S);
conversion(S);
return OK;
}
（九）实验数据及结果
输入
结果
数值：1000进制：2
数值：1348进制：2
数值：100进制：12
数值：10进制：3
选作：
（一）实验内容
实验报告
课程
数据结构及算法
实验项目
3、栈的建立及应用
成绩
专业班级
指导教师
岳静
姓名
学号
实验日期
（一）实验目的
1.掌握栈的特性及其顺序存储结构。
2.掌握顺序栈的初始化、入栈和出栈操作，并能灵活运用。
（二）实验内容
任意输入一个数学表达式，判断括号（包括大括号、中括号和小括号）是否匹配。
（三）解决思路
可将数学表达式作为字符串进行处理。依次读取字符串中每个字符，对非括号字符不作处理，若为左括号，则应等待与其匹配的右括号。在判断过程中，后读到的左括号比先读到的左括号更急于得到匹配，这一要求与栈先进后出的特点相符，因此可考虑用栈实现括号的匹配。
case '[':
case '{':push(S,ch); break;
case ')':if (pop(S,e) == ERROR || e!='(') flag = ERROR; break;
case ']':if (pop(S,e) == ERROR || e!='[') flag = ERROR; break;
if (!S.base) return(ERROR);
S.top = S.base + S.stacksize;
S.stacksize += stackINCREMENT;
}
*S.top++ = x;
return OK;
}
Status pop(Sqstack &S, SElemType &e)
{
if (S.top == S.base)return ERROR;
首先，建立一个栈结构，且初始化为空，即令栈顶指针top=0。然后由键盘上随机输入一个带括号的语句或带括号数学表达式，同时将它们保存在一个字符型数组中，再对字符数组中的每个元素进行访问，若是遇到右括号，则将栈中的栈顶元素出栈。当字符数组所有元素都访问完之后，再根据栈顶指针top的值判断左右括号是否匹配，若top=base时，则左右括号匹配，否则，左右括号不匹配。
case '}':if (pop(S,e) == ERROR || e!='{') flag = ERROR; break;
default:break;
}
}
if (flag&&ch=='\n'&&StackEmpty(S)==OK) return OK;
else return ERROR;
}
int main()
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <malloc.h>
typedef int来自百度文库Status;
typedef char SElemType;
#define stack_INIT_SIZE 100
#define stackINCREMENT 10
}
*S.top++ = x;
return OK;
}
Status pop(Sqstack &S, SElemType &e)
{
if (S.top == S.base)return ERROR;
e = *--S.top;
return OK;
}
Status GetTop(Sqstack S, SElemType &e)
SElemType *base; //栈底指针
SElemType *top; //栈顶指针
int stacksize; //栈空间
}Sqstack;
Status iniStack(Sqstack &S) //初始化栈
{//构造一个空栈S
S.base = (SElemType*)malloc(stack_INIT_SIZE * sizeof(SElemType));
if (!S.base)return(ERROR);
S.top = S.base;
S.stacksize = stack_INIT_SIZE;
return OK;
}//InitStack
status iniStack_number(Nstack &L) //初始化数字栈
{//构造一个空栈L
L.b=(ElemType*)malloc(stack_INIT_SIZE*sizeof(ElemType));
{
int N;
int n;
long e,sum=0;
printf("请输入要转化的数值和进制:\n");
scanf("%d%d",&N,&n);
while(N)
{
push(S,N % n);
N=N/n;
}
while(StackEmpty(S)==ERROR)
{
pop(S,e);
sum=sum*10+e;
}//InitStack
Status push(Sqstack &S, SElemType x)
{
if (S.top - S.base >= S.stacksize){
S.base = (SElemType *)realloc(S.base,
(S.stacksize + stackINCREMENT)*sizeof(SElemType));
在进行出栈运算时，通常在栈顶指针top=base时，就不能进行出栈运算了，否则返回错误状态。为正确判断形如“x*(y+z))”类型的表达式，可将出栈操作后的状态值可考虑进来，也就是说，当字符数组所有元素都访问完之后，若top=base且状态值为正确则左右括号匹配，否则，左右括号不匹配。
（四）实验代码
#define OK 1
#define ERROR 0
typedef struct {
SElemType *base; //栈底指针
SElemType *top; //栈顶指针
int stacksize; //栈空间
}Sqstack;
Status iniStack(Sqstack &S) //初始化栈
{
Sqstack S;
int i;
iniStack(S);
i=Compare(S);
if (i==OK)
printf("括号匹配成功！\n");
if(i==ERROR)
printf("括号匹配失败！\n");
return 0;
}
（五）实验数据及结果
输入
结果
()
((((((((
[([][])]
{[([][])()]
if (!S.base)return(ERROR);
S.top = S.base;
S.stacksize = stack_INIT_SIZE;
return OK;
}//InitStack
Status push(Sqstack &S, SElemType x)
{
if (S.top - S.base >= S.stacksize){
{
if (S.top == S.base)return ERROR;
e = *(S.top - 1);
return OK;
}
Status StackEmpty(Sqstack S)
{
if (S.base == S.top) return OK;
return ERROR;
}
Status conversion(Sqstack S)
#include <malloc.h>
typedef int Status;
typedef long SElemType;
#define stack_INIT_SIZE 100
#define stackINCREMENT 10
#define OK 1
#define ERROR 0
typedef struct {
S.base = (SElemType *)realloc(S.base,
(S.stacksize + stackINCREMENT)*sizeof(SElemType));
if (!S.base) return(ERROR);
S.top = S.base + S.stacksize;
S.stacksize += stackINCREMENT;
（六）实验内容
实现十进制数像任意进制转换。
要求：输入一个十进制数，再输入一个整数代表某种进制（例如2代表二进制），将该十进制数转换成要求的进制并输出。
（七）解决思路
采用除X（X进制）取余法。
（八）实验代码
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
e = *--S.top;
return OK;
}
Status GetTop(Sqstack S, SElemType &e)
{
if (S.top == S.base)return ERROR;
e = *(S.top - 1);
return OK;
}
Status StackEmpty(Sqstack S)
if(!L.t) return (ERROR);
L.t=L.b;
L.maxsize=stack_INIT_SIZE;
return OK;
}//InitStack
Status push(Sqstack &S, SElemType x)
{
if (S.top - S.base >= S.stacksize){
}Sqstack;
typedef struct Number
{
ElemType *b;
ElemType *t;
int maxsize;
}Nstack;
Status iniStack(Sqstack &S) //初始化栈
{//构造一个空栈S
S.base = (SElemType*)malloc(stack_INIT_SIZE * sizeof(SElemType));
#define stack_INIT_SIZE 100
#define stackINCREMENT 10
#define OK 1
#define ERROR 0
typedef struct {
SElemType *base; //栈底指针
SElemType *top; //栈顶指针
int stacksize; //栈空间
{
if (S.base == S.top) return OK;
return ERROR;
}
Status Compare(Sqstack &S)
{
int flag = OK;
char ch,e;
while ((ch=getchar())!= '\n'&& flag)
{
switch (ch)
{
case '(':
表1运算符优先级
（二）解决思路
设置两个栈——操作数栈OPTD和操作符栈OPTR。首先将表达式的起始符“#”压入操作符栈OPTR，作为表达式运算的结束标志。求值过程为自左向右扫描表达式，若当前字符是操作数，则入操作数栈，若是运算符，则比较当前运算符和操作符栈OPTR栈顶运算符的优先级，若当前运算符优先级高，则当前运算符入操作符栈OPTR；若当前运算符优先级低，则操作符栈OPTR出栈一个元素，操作数栈OPTD出栈两个元素，进行运算，将计算结果压入操作数栈OPTD，若当前运算符与栈顶元素优先级相同，则操作符栈OPTR出栈一个元素，与当前运算符抵消，然后继续扫描下一个字符，直到整个表达式求值完毕。
S.base = (SElemType *)realloc(S.base,
表达式计算是实现程序设计语言的基本问题之一，也是栈的应用的一个典型例子。设计一个程序，演示用算符优先法对算术表达式求值的过程。
以字符序列的形式从终端输入语法正确的、不含变量的整数表达式。利用表1给出的算符优先关系，实现对算术四则混合运算表达式的求值，并仿照教材的例3-1演示在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。