编写程序对表达式求值：

#include "stdio.h"

#include "malloc.h"

#define TRUE1

#define FALSE 0

#define OK 1

#define ERROR 0

#define INFEASIBLE -1

#define OVERFLOW-2

typedef int Status

#define STACK_INIT_SIZE 100

#define STACKINCREMENT 10

typedef struct{

SElemType *base

SElemType *top

int stacksize

}SqStack

//构造一个空栈

Status InitStack(SqStack *S){

S->base = (SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType))

if(!S->base)

exit(OVERFLOW)

S->top=S->base

S->stacksize=STACK_INIT_SIZE

return OK

}

//判断是否为空栈

Status StackEmpty(SqStack S){

if(S.top == S.base)

return TRUE

else

return FALSE

}

//用e返回S的顶元素

Status GetTop(SqStack S, SElemType *e){

if(S.top == S.base)

return ERROR

*e = *(S.top-1)

return OK

}

//插入e为新的顶元素

Status Push(SqStack *S, SElemType e){

if((S->top - S->base) >= S->stacksize){

S->base = (

SElemType*)realloc(S->base,

(S->stacksize+STACKINCREMENT)*sizeof(SElemType)

)

if(!S->base)

exit(OVERFLOW)

S->top = S->base +S->stacksize

S->stacksize += STACKINCREMENT

}

*(S->top)=e

S->top++

return OK

}

//删除S的顶元素，并用e返回其值

Status Pop(SqStack *S, SElemType *e){

if(S->top == S->base)

return ERROR

S->top--

*e = *(S->top)

return OK

}

//从栈底到栈顶依次对S的每个元素调用函数Visit（），一旦失败 *** 作无效

Status ListTraverse(SqStack S,Status (*visit)(SElemType)){

SElemType *p

p=S.base

for(p=S.basep<S.topp++)

(*visit)(*p)

return OK

}

//输出元素e

Status output(SElemType e){

printf("%d ",e)

return OK

}

实现表达式求值的代码：

/*计算整数表达式的值

*表达式必须以#结束

*表达式中可以出现多位数字，

*表达式中可以出现空格

*运算符包括+,-,*,/,(,)

*运算结果可以是多位整数，并以整数的形式返回

*/

typedef int SElemType /*放入堆栈的元素的类型*/

#include <ctype.h>

#include "stack_s.c"

/*判断输入的某个字符是否是运算符

*c表示输入的字符

*op数组中存放系统能识别的运算符

*/

Status in(char c,char op[]){

char *p

p=op

while(*p != '\0'){

if(c == *p)

return TRUE

p++

}

return FALSE

}

/*比较两个运算符的优先级

*a，b中存放待比较的运算符

*'>'表示a>b

*'0'表示不可能出现的比较

*/

char Precede(char a, char b){

int i,j

char pre[][7]={

/*运算符之间的优先级制作成一张表格*/

{'>','>','<','<','<','>','>'},

{'>','>','<','<','<','>','>'},

{'>','>','>','>','<','>','>'},

{'>','>','>','>','<','>','>'},

{'<','<','<','<','<','=','0'},

{'>','>','>','>','0','>','>'},

{'<','<','<','<','<','0','='}}

switch(a){

case '+': i=0break

case '-': i=1break

case '*': i=2break

case '/': i=3break

case '(': i=4break

case ')': i=5break

case '#': i=6break

}

switch(b){

case '+': j=0break

case '-': j=1break

case '*': j=2break

case '/': j=3break

case '(': j=4break

case ')': j=5break

case '#': j=6break

}

return pre[i][j]

}

/*进行实际的运算

*a，b中分别以整数的形式存放两个待运算的 *** 作数

*theta中存放代表 *** 作符的字符

*结果以整数的形式返回

*/

int Operate(int a, char theta, int b){

int i,j,result

i=a

j=b

switch(theta) {

case '+': result = i + jbreak

case '-': result = i - jbreak

case '*': result = i * jbreak

case '/': result = i / jbreak

}

return result

}

/*从输入缓冲区中获得下一个整数或运算符，并通过n带回到主调函数

*返回值为1表示获得的是运算符

*返回值为0表示获得的是整形 *** 作数

*/

int getNext(int *n){

char c

*n=0

while((c=getchar())==' ') /*跳过一个或多个空格*/

if(!isdigit(c)){/*通过函数判断如果字符不是数字，那么只能是运算符*/

*n=c

return 1

}

do{ /*能执行到该条语句，说明字符是数字，此处用循环获得连续的数字*/

*n=*n*10+(c-'0') /*把连续的数字字符转换成相对应的整数*/

c=getchar()

}while(isdigit(c))/*如果下一个字符是数字，进入下一轮循环*/

ungetc(c,stdin) /*新读入的字符不是数字，可能是运算符,为了不影响下次读入，把该字符放回到输入缓冲区*/

return 0

}

int EvaluateExpression(){

int n

int flag

int c

char x,theta

int a,b

char OP[]="+-*/()#"

SqStack OPTR

SqStack OPND

InitStack(&OPTR)

Push(&OPTR,'#')

InitStack(&OPND)

flag=getNext(&c)

GetTop(OPTR, &x)

while(c!='#' || x != '#')

{

if(flag == 0)

{

Push(&OPND,c)

flag = getNext(&c)

}else

{

GetTop(OPTR, &x)

switch(Precede(x, c))

{

case '<'://栈顶元素优先级低

Push(&OPTR,c)

flag = getNext(&c)

break

case '='://脱括号并接受下一字符

Pop(&OPTR,&x)

flag = getNext(&c)

break

case '>'：// 退栈并将运算结果入栈

Pop(&OPTR, &theta)

Pop(&OPND,&b)

Pop(&OPND,&a)

Push(&OPND, Operate(a, theta, b))

break

}

}

GetTop(OPTR, &x)

}

GetTop(OPND, &c)

return c

}

void main(){

int c

printf("Please input one expression:")

c=EvaluateExpression()

printf("Result=%d\n",c)

getch()

}

//参考代码

#include <stdio.h>

#include <string.h>

typedef int SElemType // 栈的元素类型

#define STACK_INIT_SIZE 10 // 存储空间初始分配量 

#define STACKINCREMENT 2 // 存储空间分配增量 

/*

 *顺序栈的结构体

 * */

typedef struct SqStack

{

SElemType *base // 在栈构造之前和销毁之后，base的值为NULL 

SElemType *top // 栈顶指针 

int stacksize // 当前已分配的存储空间，以元素为单位 

}SqStack

/*

 *构造一个栈

 * */

int InitStack(SqStack *S)

{

// 为栈底分配一个指定大小的存储空间

(*S).base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType))

if( !(*S).base )

exit(0) // 存储分配失败 

(*S).top = (*S).base // 栈底与栈顶相同表示一个空栈

(*S).stacksize = STACK_INIT_SIZE

return 1

}

/*

 *获取栈顶元素

 * */

int GetTop(SqStack S,SElemType *e)

{

if(S.top > S.base)

{

*e = *(S.top-1) // 栈顶指针的下一个位置为栈顶元素

return 1

}

else

return 0

}

/*

 *入栈（压栈）

 * */

int Push(SqStack *S, SElemType e)

{

if((*S).top - (*S).base >= (*S).stacksize) // 栈满，追加存储空间 

{

(*S).base = (SElemType *)realloc((*S).base, 

((*S).stacksize + STACKINCREMENT) * sizeof(SElemType))

if( !(*S).base )

exit(0) // 存储分配失败 

(*S).top = (*S).base+(*S).stacksize

(*S).stacksize += STACKINCREMENT

}

*((*S).top)++=e

// 这个等式的++ * 优先级相同，但是它们的运算方式，是自右向左

return 1

}

/*

 *出栈

 * */

int Pop(SqStack *S,SElemType *e)

{

if((*S).top == (*S).base)

return 0

*e = *--(*S).top

// 这个等式的++ * 优先级相同，但是它们的运算方式，是自右向左

return 1

}

/*

 *判断优先级

 * */

SElemType Precede(SElemType t1,SElemType t2)

{

SElemType f

switch(t2)

{

case '+':

case '-':

if(t1=='('||t1=='#')

f='<'

else

f='>'

break

case '*':

case '/':

if(t1=='*'||t1=='/'||t1==')')

f='>'

else

f='<'

break

case '(':

if(t1==')')

{

printf(ERROR1

)

exit(0)

}

else

f='<'

break

case ')':

switch(t1)

{

case '(':

f='='

break

case '#':

printf(ERROR2

)

exit(0)

default:

f='>'

}

break

case '#':

switch(t1)

{

case '#':

f='='

break

case '(':

printf(ERROR3

)

exit(0)

default: 

f='>'

}

}

return f

}

/*

 *搜索运算符

 * */

int In(SElemType c)

{

switch(c)

{

case'+':

case'-':

case'*':

case'/':

case'(':

case')':

case'#':return 1

default:return 0

}

}

/*

 *运算

 * */

SElemType Operate(SElemType a,SElemType theta,SElemType b)

{

SElemType c

a=a-48 //ASCII值转化为对应的十进制值

b=b-48 //ASCII值转化为对应的十进制值

switch(theta)

{

case'+':

c=a+b+48

break

case'-':

c=a-b+48

break

case'*':

c=a*b+48

break

case'/':c=a/b+48

}

return c

}

/*

 *比较运算符优先级

 * */

SElemType EvaluateExpression()

{

SqStack OPTR,OPND

SElemType a,b,c,x,theta

InitStack(&OPTR)

Push(&OPTR,'#')

InitStack(&OPND)

c=getchar()

GetTop(OPTR,&x)

while(c!='#'||x!='#')

{

if(In(c)) // 是7种运算符之一 

switch(Precede(x,c))

{

         case'<':

 Push(&OPTR,c) // 栈顶元素优先权低 

 c=getchar()

 break

         case'=':

 Pop(&OPTR,&x) // 脱括号并接收下一字符 

 c=getchar()

 break

         case'>':

 Pop(&OPTR,&theta) // 退栈并将运算结果入栈 

 Pop(&OPND,&b)

 Pop(&OPND,&a)

 Push(&OPND,Operate(a,theta,b))

 break

}

else if(c>='0'&&c<='9') // c是 *** 作数 

{

Push(&OPND,c)

c=getchar()

}

else // c是非法字符 

{

printf(非法字符！！

)

exit(0) 

}

GetTop(OPTR,&x)

}

GetTop(OPND,&x)

return x

}

int main()

{

printf(请输入算术表达式,并以#结束)

printf("%d",EvaluateExpression())

return 0

}

---