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);}elsereturn -1;}elsereturn -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);
}