1、算术表达式 求值
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
typedef struct Node
{
int data;
struct Node * pNext;
}NODE,* PNODE;
typedef struct Stack
{
PNODE pTop;
PNODE pBottom;
}STACK,*PSTACK;
//初始化
void initStack(PSTACK);
//判断栈是否为空
bool isEmpty(PSTACK);
//压栈
void push(PSTACK,int);
//出栈
bool pop(PSTACK,int* pVal);
//返回栈顶元素
int top(PSTACK pS);
void initStack(PSTACK pS)
{
pS->pTop=(PNODE)malloc(sizeof(NODE));
if (NULL == pS->pTop)
{
printf("分配内存失败，程序终止！\n");
exit(-1);
}
else
{
pS->pBottom = pS->pTop;
pS->pTop->pNext = NULL;
}
}
bool isEmpty(PSTACK pS)
{
if (pS->pTop == pS->pBottom)
return true;
else
return false;
}
void push(PSTACK pS,int val)
{
PNODE pNew = (PNODE)malloc(sizeof(NODE));
if (NULL == pNew)
{
printf("分配内存失败，程序终止！\n");
exit(-1);
}
pNew->data = val;
pNew->pNext = pS->pTop;
pS->pTop = pNew;
}
bool pop(PSTACK pS)
{
if (isEmpty(pS)){
return false;
}
else
{
PNODE p = pS->pTop;
pS->pTop = p->pNext;
free(p);
p = NULL;
return true;
}
}
int top(PSTACK pS)
{
PNODE p = pS->pTop;
int val = p->data;
return val;
}
int callExpr(char expr[],int* result)
{
STACK s;
initStack(&s);
int num,a,b;
char* ptr;
ptr=expr;
while(*ptr != '\0')
{
if(*ptr == ' ')
{
ptr++;
continue;
}
else if(isdigit(*ptr))
{
num=0;
while(*ptr>='0' && *ptr<='9')
{
num = num * 10 + *ptr - '0';
ptr++;
}
push(&s,num);
}
else if( *ptr == '+' || *ptr == '-' || *ptr == '*' || *ptr == '/')
{
if(!isEmpty(&s))
{
a=top(&s);
pop(&s);
if(!isEmpty(&s))
{
b=top(&s);
pop(&s);
}
else
return -1;
}
else
return -1;
switch(*ptr)
{
case '+': push(&s,b+a);
break;
case '-': push(&s,b-a);
break;
case '*': push(&s,b*a);
break;
case '/': push(&s,b/a);
break;
}
}
else
{
return -1;
}
ptr++;
}
if(!isEmpty(&s))
{
*result=top(&s);
pop(&s);
if(!isEmpty(&s))
{
return -1;
}
return 0;
}
return -1;
}
/**栈的应用：计算表达式46+5*(120-37) 后缀表达式为"46 5 120 37 - * +"
计算过程如下
1 依次将46 5 120 37 压入栈中
2 遇到"-",弹出37和120，计算120-37，得83，将其压入栈中
遇到"*"，弹出83和5，计算5*83，得到415，将其压入栈中
遇到"+"，弹出415和46，计算46+415，得到461，将其压入栈中
3 表达式结束，计算完成，栈顶为计算结果
*/
void main()
{
char a[] ="46 5 120 37 - * +";
int val=0;
callExpr(a,&val);
printf("%d\n",val);
}