栈与栈的应用

一、实验目的：

1.了解栈逻辑结构的特点，掌握栈的基本操作，为应用奠定基础。

2.学习应用栈解决实际问题。

二、实验内容：

1.利用栈实现数制转换

2.表达式括号匹配问题

三、实验要求

1．用C++/C完成算法设计和程序设计并上机调试通过。

2．分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要给出算法设计小结和心得。

//你看看吧..这是我写过的。。。注释很详细

//表达式求值
//By:jimly
//10/10/2009
//例如：输入2+2（4-6*3）=
//以"="结束,然后回车即出结果
#include <stdio.h>
#include <conio.h>
#include <windows.h>
#include <assert.h>
typedef float ElemType;
typedef struct Stack
{
ElemType *base; // 栈基址
ElemType *top; // 栈顶
int stacksize; // 栈存储空间的尺寸
} SqStack;

bool InitStack(SqStack *S);
bool InitStack(SqStack *S);
void DestroyStack(SqStack *S);
bool StackEmpty(SqStack S);
int StackLength(SqStack S);
ElemType GetTop(SqStack S, ElemType *e);
void StackTraverse(SqStack S, void (*fp)(ElemType));
bool Push(SqStack *S, ElemType e);
bool Pop(SqStack *S, ElemType *e);

char Precede(char A1,char A2);
ElemType Operate(ElemType a,ElemType theta,ElemType b);
bool In(char c,char op[]);
ElemType EvaluateExpression();
void Menu();

//////////////////////////////////////////////
// Eval_exdivssion.cpp 表达式求值实现函数 //
//////////////////////////////////////////////

char Precede(char A1,char A2)
{
if (A1 == '+' || A1 == '-')
{
if (A2 == '+' || A2 == '-' || A2 == ')' || A2 == '=')
{
return '>';
}
else
return '<';
}
if (A1 == '*' || A1 == '/')
{
if (A2 == '(')
{
return '<';
}
else
return '>';
}
if (A1 == '(')
{
if (A2 == ')')
{
return '=';
}
if (A2 == '=')
{
return 'E';
}
else
return '<';
}
if (A1 == ')')
{
if (A2 == '(')
{
return 'E';
}
if (A2 == '=')
{
return 'E';
}
else
return '>';
}
if (A1 == '=')
{
if (A2 == '=')
{
return '=';
}
else
return '<';
}
else
return '=';
}

ElemType Operate(ElemType a,ElemType theta,ElemType b)
{
switch(char(theta))
{
case '+':
return a += b;
break;
case '-':
return a -= b;
break;
case '*':
return a *= b;
break;
case '/':
if(b==0)
{
printf("除数不能为0！！\n");
exit(0);
}
return a /= b;
break;
}

return 0;
}

bool In(char c,char op[])
{
for (int i = 0;i<7;i++)
{
if (op[i] == c)
return true;
}
return false;
}

ElemType EvaluateExpression()
{
SqStack OPTR; //运算符栈
SqStack OPND; //运算数栈
char Ct = '='; //判断是否结束的标识
int i = 0,j = 1;
ElemType e = 0,t = 0,c;
char op[7] = {'+','-','*','/','(',')','='};

InitStack(&OPTR); //初始化
Push(&OPTR,Ct);
InitStack(&OPND); //初始化

c = (float)getchar();
while (c!='=' || GetTop(OPTR,&e)!='=')
{
if (!In((char)c,op)) //不是运算e符进栈
{
while(!In((char)c,op)) //可以是几位数
{
t = t*10+(c-48);
c = (float)getchar();
}
Push(&OPND,t);
t = 0;
}

else
{
switch (Precede((char)GetTop(OPTR,&e),(char)c))
{
case '<'://栈顶元素优先权低
Push(&OPTR,c);
c = (float)getchar();
break;
case '='://脱括号并接受下个字符
ElemType x;
Pop(&OPTR,&x);
c = (float)getchar();
break;
case '>'://退栈并将运算结果入栈
ElemType b,theta,a;
Pop(&OPTR,&theta);
Pop(&OPND,&b);
Pop(&OPND,&a);
Push(&OPND,Operate(a,theta,b));
break;
case 'E':
printf("括号不匹配！！\n");
exit(0);
break;

}
}
}
ElemType tem = GetTop(OPND,&e);
DestroyStack(&OPND);
DestroyStack(&OPTR);
return tem;
}

const int STACK_INIT_SIZE = 100; // 初始分配的长度
const int STACKINCREMENT = 10; // 分配内存的增量

bool InitStack(SqStack *S)
{
assert(S != NULL);
S->base = (ElemType *)malloc(sizeof(ElemType) * STACK_INIT_SIZE);

if(S->base == NULL) return false;

S->top = S->base;
S->stacksize = STACK_INIT_SIZE;

return true;
}

void DestroyStack(SqStack *S)
{
assert(S != NULL);

free(S->base);
S->top = S->base = NULL;
}

bool StackEmpty(SqStack S)
{
assert((S.base != NULL) && (S.top != NULL));
return(S.base == S.top);
}

int StackLength(SqStack S)
{
assert((S.base != NULL) && (S.top != NULL));
return(S.top-S.base);
}

ElemType GetTop(SqStack S, ElemType *e)
{
assert((S.base != NULL) && (S.top != NULL));
if(StackEmpty(S)) return false;

*e = *(S.top-1);
return *e;
}

void StackTraverse(SqStack S, void (*fp)(ElemType))
{
assert((S.base != NULL) && (S.top != NULL));
for(; S.base<S.top; S.base++) (*fp)(*S.base);
}

bool Push(SqStack *S, ElemType e)
{
if (S->top - S->base>=S->stacksize)
{
S->base = (ElemType *)realloc(S->base,(S->stacksize + STACKINCREMENT) * sizeof(ElemType));
if (!S->base)
exit(0);
S->top = S->base + S->stacksize;
S->stacksize += STACKINCREMENT;
}
*S->top++ = e;

return true;
}

bool Pop(SqStack *S, ElemType *e)
{
if(S == NULL) return false;
assert((S->base != NULL) && (S->top != NULL));
if(StackEmpty(*S)) return false;

*e = *(--S->top);
return true;
}

//////菜单///////
void Menu()
{
printf("表达式求值模拟程序\n\n");

printf("功能菜单：\n");
printf("==============\n");
printf("[1] 输入表达式并求值\n");
printf("[0] 退出 \n");
printf("==============\n");
printf("请输入你的选择(0~1)（以回车结束）：");
}

///////// 主函数 ///////////
//////////////////////////////
int main()
{
char ch = ' ',tp;

do
{
system("cls");
Menu();
ch = getchar();
if (ch == '0')
break;
tp = getchar();
printf("请输入一个表达式（最后输入”=“,然后回车出结果）：");
printf("这个表达式结果为：%g\n",EvaluateExpression());
tp = getchar();
printf("任意键继续...");
getch();
} while (true);

return 0;
}//end