| 前几天做的一个数据结构上机实验
/*===========================================================*/
/* ** 中缀表达式的求值 ** */
/*函数个数：4 包含2个自定义头文件(seqstack.h seqstack1.h) */
/*作者：踏网无痕 */
/*修改时间：31/05/04 */
/*在VC++6.0下调试 */
/*===========================================================*/
#include
#include
#include
#include
typedef float DataType; /*运算数的类型定义*/
#include "seqstack.h"
typedef struct /*运算符的类型定义*/
{
char op;
int inputprecedence; /*读入时的优先级*/
int stackprecedence; /*栈内的优先级*/
}DataType1;
#include "seqstack1.h"
DataType1 MathPotr(char); /*给读入的运算符和左右括号配备优先级*/
void Evaluate(SeqStack *,DataType1);
/*执行从运算符栈弹出的运算符号所要求的运算*/
void Infix(char *); /*将数、符分类压栈*/
int isoptr(char); /*判断字符是否为运算符或左括号*/
/*
*主函数
*输入：空
*返回：空
*/
void main(void)
{
char str[50]; /*声明接收表达式的字符串*/
printf("Please input the expression(use \"=\" to end):");
gets(str); /*键盘读入用户的表达式*/
Infix(str); /*将表达式进行计算*/
}
/*
*功能：给读入的运算符和左右括号配备优先级
*输入：运算符和左右括号
*返回：运算符
*/
DataType1 MathOptr(char ch)
{
DataType1 optr;
optr.op=ch;
switch(optr.op)
{
case '+':
case '-':
optr.inputprecedence=1;
optr.stackprecedence=1;
break;
case '*':
case '/':
optr.inputprecedence=2;
optr.stackprecedence=2;
break;
case '(':
optr.inputprecedence=3;
optr.stackprecedence=-1;
break;
case')':
optr.inputprecedence=0;
optr.stackprecedence=0;
break;
}
return optr;
}
/*
*功能：执行从运算符栈弹出的运算符号optr所要求的运算
*输入：（运算数栈指针类型）运算数栈，（运算符栈元素类型）
*返回：空
*/
void Evaluate(SeqStack *OpndStack,DataType1 optr)
{
DataType opnd1,opnd2; /*声明两个运算数*/
opnd1=popStack(OpndStack); /*从数栈中弹出第一个数*/
opnd2=popStack(OpndStack); /*从数栈中弹出第二个数*/
switch(optr.op) /*由运算符决定运算数的计算规则*/
{
case'+':
pushStack(OpndStack,opnd2+opnd1);
break;
case'-':
pushStack(OpndStack,opnd2-opnd1);
break;
case'*':
pushStack(OpndStack,opnd2*opnd1);
break;
case'/':
pushStack(OpndStack,opnd2/opnd1);
break;
}
}
/*
*功能：将数、符分类压栈
*输入：（字符串指针）要分类处理的字符串
*返回：空
*/
void Infix(char *str)
{
int i; /*数字字符串的计数变量*/
int k; /*中缀表达式串的字符计数变量*/
int n=strlen(str); /*中缀表达式串的长度*/
char ch; /*用件处理的字符*/
char numstr[10]; /*存储数字字符串*/
DataType opnd; /*临时存储一个数字*/
DataType1 optr; /*临时存储一个运算符*/
SeqStack OpndStack; /*运算数栈*/
SeqStack1 OptrStack; /*运算符栈*/
setStack(&OpndStack,n); /*初始化运算数栈*/
setStack1(&OptrStack,n);/*初始化运算符栈*/
k=0; /*标记表达式字符串的下标*/
ch=str[k]; /*将字符串的第一个赋给ch*/
while(ch!='=')
/*如果是数字字符或小数点*/
if(isdigit(ch)||ch=='.')
{
for(i=0;isdigit(ch)||ch=='.';i++)
{
numstr=ch;
k++;
ch=str[k];
}
numstr='\0';
opnd=(float)atof(numstr);
/*将字符串转化为实数*/
pushStack(&OpndStack,opnd);
}
else
{
/*如果是运算符或左括号*/
if(isoptr(ch))
{
optr=MathOptr(ch);
while(!isStackEmpty1(&OptrStack)&&getTopData1(&OptrStack).stackprecedence>=optr.inputprecedence)
/*如果新进栈的算符优先级大的，则弹出数栈中的元素，计算后把结果压入数栈*/
Evaluate(&OpndStack,popStack1(&OptrStack));
pushStack1(&OptrStack,optr);/*算符入栈*/
k++;
ch=str[k];
}
/*如果是右括号*/
else if(ch==')')
{
optr=MathOptr(ch);
while(!isStackEmpty1(&OptrStack)&&getTopData1(&OptrStack).stackprecedence>=optr.inputprecedence)
Evaluate(&OpndStack,popStack1(&OptrStack));
popStack1(&OptrStack); /*将栈中的左括号弹出*/
k++;
ch=str[k];
}
}
/*如果运算符栈非空*/
while(!isStackEmpty1(&OptrStack))
Evaluate(&OpndStack,popStack1(&OptrStack));
opnd=popStack(&OpndStack);
printf("%-6.2f\n",opnd); /*输出计算结果*/
freeStack(&OpndStack); /*释放数栈空间*/
freeStack1(&OptrStack); /*释放算符栈空间*/
}
/*
*功能：判断字符是否为运算符或左括号
*输入：字符
*返回：1（是），0（否）
*/
int isoptr(char ch)
{
return(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='(');
}
/*
* @SeqStack11.h 1.0 04/05/21
*
* @Author 踏网无痕
*
* @实现对顺序栈的基本操作，要求用户用已有类型定义DataType11
*/
typedef struct
{
DataType1 *data;
int max;
int top;
}SeqStack1;
/*
*构造函数 建立数组长度为n的空栈
*输入：（栈类型指针）要初始化的栈的地址，（整型）栈长度
*返回：空
*/
void setStack1(SeqStack1 *s,int n)
{
s->data=(DataType1 *)malloc(n*sizeof(DataType1));
if(s->data==NULL)
{
printf("Overflow!\n");
exit(1);
}
s->max=n;
s->top=-1;
}
/*
*析构函数 释放数组空间
*输入：（栈类型指针）要释放栈的地址
*返回：空
*/
void freeStack1(SeqStack1 *s)
{
free(s->data);
}
/*
*获得栈中数据个数
*输入：（栈类型指针）要求数据个数的栈的地址
*返回：（整型）栈中数据的个数
*/
int getStackSize1(SeqStack1 *s)
{
return(s->top+1);
}
/*
*判断栈是否为空
*输入：（栈类型指针）要判断的栈的地址
*返回：（整型1或整型0）1为空，0不空
*/
int isStackEmpty1(SeqStack1 *s)
{
return(s->top==-1);
}
/*
*判断栈是否已满
*输入：（栈类型指针）要判断的栈的地址
*返回：（整型1或整型0）1为满，0不满
*/
int isStackFull1(SeqStack1 *s)
{
return(s->top==s->max-1);
}
/*
*取栈顶元素
*输入：（栈类型指针）要操作的栈的地址
*返回：（用户定义类型）栈顶元素的值
*/
DataType1 getTopData1(SeqStack1 *s)
{
if(isStackEmpty1(s))
{
printf("Stack is empty!\n");
exit(1);
}
return(s->data[s->top]);
}
/*
*元素入栈
*输入：（栈类型指针）要操作的栈的地址，（用户定义类型）要入栈的元素值
*返回：空
*/
void pushStack1(SeqStack1 *s,DataType1 item)
{
if(isStackFull1(s))
{
printf("Stack is full!\n");
exit(1);
}
s->top++;
s->data[s->top]=item;
}
/*
*元素出栈
*输入：（栈类型指针）要操作的栈的地址
*返回：（用户定义类型）出栈的元素值
*/
DataType1 popStack1(SeqStack1 *s)
{
if(isStackEmpty1(s))
{
printf("Stack is empty!\n");
exit(1);
}
s->top--;
return(s->data[s->top+1]);
}
/*
*清空栈
*输入：（栈类型指针）要操作的栈的地址
*返回：空
*/
void clearStack1(SeqStack1 *s)
{
s->top=-1;
}
/*
* @seqstack.h 1.0 04/05/16
*
* @Author 踏网无痕
*
* @实现对顺序栈的基本操作，要求用户用已有类型定义DataType
*/
typedef struct
{
DataType *data;
int max;
int top;
}SeqStack;
/*
*构造函数 建立数组长度为n的空栈
*输入：（栈类型指针）要初始化的栈的地址，（整型）栈长度
*返回：空
*/
void setStack(SeqStack *s,int n)
{
s->data=(DataType *)malloc(n*sizeof(DataType));
if(s->data==NULL)
{
printf("Overflow!\n");
exit(1);
}
s->max=n;
s->top=-1;
}
/*
*析构函数 释放数组空间
*输入：（栈类型指针）要释放栈的地址
*返回：空
*/
void freeStack(SeqStack *s)
{
free(s->data);
}
/*
*获得栈中数据个数
*输入：（栈类型指针）要求数据个数的栈的地址
*返回：（整型）栈中数据的个数
*/
int getStackSize(SeqStack *s)
{
return(s->top+1);
}
/*
*判断栈是否为空
*输入：（栈类型指针）要判断的栈的地址
*返回：（整型1或整型0）1为空，0不空
*/
int isStackEmpty(SeqStack *s)
{
return(s->top==-1);
}
/*
*判断栈是否已满
*输入：（栈类型指针）要判断的栈的地址
*返回：（整型1或整型0）1为满，0不满
*/
int isStackFull(SeqStack *s)
{
return(s->top==s->max-1);
}
/*
*取栈顶元素
*输入：（栈类型指针）要操作的栈的地址
*返回：（用户定义类型）栈顶元素的值
*/
DataType getTopData(SeqStack *s)
{
if(isStackEmpty(s))
{
printf("Stack is empty!\n");
exit(1);
}
return(s->data[s->top]);
}
/*
*元素入栈
*输入：（栈类型指针）要操作的栈的地址，（用户定义类型）要入栈的元素值
*返回：空
*/
void pushStack(SeqStack *s,DataType item)
{
if(isStackFull(s))
{
printf("Stack is full!\n");
exit(1);
}
s->top++;
s->data[s->top]=item;
}
/*
*元素出栈
*输入：（栈类型指针）要操作的栈的地址
*返回：（用户定义类型）出栈的元素值
*/
DataType popStack(SeqStack *s)
{
if(isStackEmpty(s))
{
printf("Stack is empty!\n");
exit(1);
}
s->top--;
return(s->data[s->top+1]);
}
/*
*清空栈
*输入：（栈类型指针）要操作的栈的地址
*返回：空
*/
void clearStack(SeqStack *s)
{
s->top=-1;
} |
