数据结构栈的应用 计算器 能实现加减乘除 括号匹配 浮点运算,表达是排错的中缀式求值
//*******************************************************************//mlist.h头文件:
//*******************************************************************//
#define STACK_SIZE 100
#define STACKINCREMENT 10
typedef union {
char c;
float data;
} EleType;//构造数据类型共用一个栈;
typedef struct {
EleType *top;
EleType *base;
int size;
} Stack;
Stack * CreateStack(void);
void ClearStack(Stack *stack);
void DestoryStack(Stack *stack);
int StackEmpty(Stack *stack);
int GetTop(Stack *stack, EleType *data);
int Push(Stack *stack, EleType data);
int Pop(Stack *stack, EleType *data);
Stack * CreateStack(void)
{
Stack *stack;
stack = (Stack *)malloc(sizeof(Stack));
if (!stack) return 0;
stack->base = (EleType *)malloc(sizeof(EleType)*STACK_SIZE);
if (!stack->base) { free(stack); return 0; }
stack->top = stack->base;
stack->size = STACK_SIZE;
return stack;
}
void ClearStack(Stack *stack)
{
stack->top = stack->base;
stack->size = STACK_SIZE;
}
void DestoryStack(Stack *stack)
{
ClearStack(stack);
free(stack->base);
free(stack);
}
int StackEmpty(Stack *stack)
{
if (stack->top - stack->base == 0) return 1;
return 0;
}
int GetTop(Stack *stack, EleType *data)
{
if (StackEmpty(stack)) return 0;
*data = *(stack->top-1);
return 1;
}
int Push(Stack *stack, EleType data)
{
if (stack->top - stack->base >= stack->size)
{
stack->base = (EleType *)realloc(stack->base,
(stack->size + STACKINCREMENT)*sizeof(EleType));
if (!stack->base) return 0;
stack->top = stack->base + stack->size;
stack->size += STACKINCREMENT;
}
*(stack->top++) = data;
return 1;
}
int Pop(Stack *stack, EleType *data)
{
EleType *p;
if (StackEmpty(stack)) { printf("error!\n");return 0;}
*data = *(--stack->top);
return 1;
}
//*************************************************************************//
主程序test.c:
//*************************************************************************//
#include "stdlib.h"
#include "mlist.h"
char op[7] = {'+','-','*','/','(',')','#'};
char prir[7][7] = {{'>', '>', '<', '<', '<', '>', '>'},
{'>', '>', '<', '<', '<', '>', '>'},
{'>', '>', '>', '>', '<', '>', '>'},
{'>', '>', '>', '>', '<', '>', '>'},
{'<', '<', '<', '<', '<', '=', 'e'},
{'>', '>', '>', '>', 'e', '>', '>'},
{'<', '<', '<', '<', '<', 'e', '='}};
float Operate(float a, char theta, float b)
{
switch(theta)
{
case '+':return (a+b);
case '-':return (a-b);
case '*':return (a*b);
case '/':return (a/b);
default: return 0;
}
}
int In(char input)
{
int n;
for (n=0; n<7; n++)
{
if (input == op[n]) return 1;
}
return 0;
}
char pror(char a, char b)
{
int i,j;
char c;
for (i=0; i<7; i++)
{
if (a == op[i]) break;
}
for (j=0; j<7; j++)
{
if (b == op[j]) break;
}
return prir[i][j];
}
float Expression(void)
{
Stack *OPTR;
Stack *OPND;
char exp[81],temp[20],*c;
EleType Data,a,b,value,theta,x,m;
OPTR = CreateStack();
if (!OPTR) return 0;
m.c = '#';
Push(OPTR, m);
OPND = CreateStack();
if (!OPND) return 0;
printf("input:\n");
gets(exp);
strcat(exp, "#");
c = exp;
if(exp[0]=='-')
{
x.data=0;
Push(OPND,x);
}
while (*c!='#'||(GetTop(OPTR, &x), x.c!='#'))
{
if (!In(*c))
{
int i=0;
while (!In(*c))
{
temp[i++] = *c;
c++;
}
temp[i] = '\0';
Data.data = (float)atof(temp);
Push(OPND, Data);
}
else
{
if(*c=='(' &&*(c+1)=='-')
{
x.data=0;
Push(OPND,x);
}
if(*c=='(' && *(c+1)==')'){printf("error");return 0;}
GetTop(OPTR, &x);
switch(pror(x.c, *c))
{
case'<': m.c = *c;
Push(OPTR, m);
c++; break;
case'=': Pop(OPTR, &x);
c++; break;
case'>': Pop(OPTR, &theta);
Pop(OPND, &a);
Pop(OPND, &b);
m.data = Operate(b.data, theta.c, a.data);
Push(OPND, m);
break;
case'e': printf("2inpur error!\n"); return 0;
}
}
}
Pop(OPND, &value);
if (!StackEmpty(OPND)) {printf("3intput error!\n"); return 0;}
return value.data;
}
void main()
{
float value;
value = Expression();
printf("result=%f\n", value);
}