c++中缀表达式求值

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define MAXSIZE 100

//数字栈

typedef struct oprd{

double data[MAXSIZE]

int top

}OPRD

//运算符栈

typedef struct optr{

char data[MAXSIZE]

int top

}OPTR

//因为涉及到两个栈的 *** 作,所以将栈相关的 *** 作用宏定义写成函数,

//这样就具有了通用性

//初始化栈

#define InitStack(StackType, stack) \

{ \

*stack = (StackType *)malloc(sizeof(StackType)) \

*stack->top = -1 \

}

//判栈空

#define EmptyStack(stack) \

( \

stack->top == -1 \

)

//判栈满

#define FullStack(stack) \

( \

stack->top == MAXSIZE - 1 \

)

//入栈

#define PushStack(stack, value) \

{ \

if (!FullStack(stack)){ \

stack->top++ \

stack->data[stack->top] = value \

} \

else{ \

printf("栈已满,无法入栈\n") \

exit(-1) \

} \

}

//出栈

#define PopStack(stack, value) \

{ \

if (!EmptyStack(stack)){ \

*value = stack->data[stack->top] \

stack->top-- \

} \

else{ \

printf("栈已空,无法出栈\n") \

exit(-1) \

} \

}

//取栈顶元素

#define GetStackTop(stack, value) \

{ \

if (!EmptyStack(stack)){ \

*value = stack->data[stack->top] \

} \

else{ \

printf("栈为空,无法取栈顶元素\n") \

} \

}

//优先级表

char compare(char ch, char top)

{

switch(ch){

case '+':

case '-':

if (top == '+' || top == '-' || top == '*' || top == '/')

return '<' //扫描的小于栈顶

else

return '>' //扫描的大于栈顶

break

case '*':

case '/':

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

return '<'

else

return '>'

break

case '(':

if(top == ')'){

printf("输入有误!\n") exit(-1)

}

return '>'

break

case ')':

if (top == '(')

return '='

else if(top == '#'){

printf("输入有误!\n")

exit(-1)

}

else{

return '<'

}

break

case '#':

return '<'

}

}

//输入表达式并计算结果

double CalculateExp(void)

{

double result, tempNum1, tempNum2

double data = 0, expn

char ch, topSign, point = 'n', num = 'n'

OPTR *sign

OPRD *number

InitStack(OPTR, &sign)

InitStack(OPRD, &number)

PushStack(sign, '#')

printf("请输入表达式：")

ch = getchar()

GetStackTop(sign, &topSign)

while(ch != '#' || topSign != '#'){

if ('0' <= ch && ch <= '9' || ch == '.'){

if (ch == '.' && point == 'y'){

printf("表达式输入有误!\n")

exit(-1)

}

else if (ch == '.' && point == 'n'){

point = 'y'

expn = 0.1

}

else{

if (point == 'y'){

data = data + expn * (ch - '0')

expn *= 0.1

}

else{

data = data * 10 + (ch - '0')

}

num = 'y'

}

ch = getchar()

}

else if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(' || ch == ')' || ch == '#'){

if (num == 'y'){

PushStack(number, data)

num = 'n' point = 'n'

data = 0

}

GetStackTop(sign, &topSign)

switch(compare(ch, topSign)){

case '<': //扫描运算符优先级小于栈顶元素

PopStack(sign, &topSign)

PopStack(number, &tempNum1)

PopStack(number, &tempNum2)

switch(topSign){

case '+': result = tempNum1 + tempNum2 break

case '-': result = tempNum1 - tempNum2 break

case '*': result = tempNum1 * tempNum2 break

case '/': result = tempNum2 / tempNum1 break

}

PushStack(number, result)

break

case '>': //扫描运算符优先级大于栈顶元素

PushStack(sign, ch)

ch = getchar()

break

case '=': //扫描运算符为右括号,匹配到了左括号

PopStack(sign, &topSign)

ch = getchar()

break

}

}

else if (ch == '\n'){

ch = '#'

}

else{

printf("输入的表达式有误!\n")

exit(-1)

}

GetStackTop(sign, &topSign)

}

PopStack(number, &result) //将结果从栈中取出来

if (!EmptyStack(number)){   //如果取出后栈不为空则表示输入的表达式不正确

printf("表达式有误!\n")

exit(-1)

}

return result

}

int main(void)

{

printf("%lf\n", CalculateExp())

return 0

}

include#include#include//判断是否为字符的函数的头文件#definemaxsize100typedefintelemtypetypedefstructsqstacksqstack//由于sqstack不是一个类型而structsqstack才是charch[7]=//把符号转换成一个字符数组intf1[7]=//栈内元素优先级intf2[7]=//栈外的元素优先级structsqstack{elemtypestack[maxsize]inttop}voidInitstack(sqstack*s){s->top=0}voidPush(sqstack*s,elemtypex){if(s->top==maxsize-1)printf("Overflow\n")else{s->top++s->stack[s->top]=x}}voidPop(sqstack*s,elemtype*x){if(s->top==0)printf("underflow\n")else{*x=s->stack[s->top]s->top--}}elemtypeGettop(sqstacks){if(s.top==0){printf("underflow\n")return0}elsereturns.stack[s.top]}elemtypef(charc){switch(c){case'+':return0case'-':return1case'*':return2case'/':return3case'(':return4case')':return5default:return6}}charprecede(charc1,charc2){inti1=f(c1)inti2=f(c2)//把字符变成数字if(f1[i1]>f2[i2])//通过原来设定找到优先级return'>'elseif(f1[i1]':Pop(&OPTR,&theta)Pop(&OPND,&b)Pop(&OPND,&a)//注意这里是谁先出栈Push(&OPND,Operate(a,theta,b))break}}}//在这里判断是否以运算符结束是不对的return(Gettop(OPND))}main(){intresultprintf("输入你的算术表达式：\n")result=EvaluateExpression()printf("结果是:%d\n",result)return0}:本计算器利用堆栈来实现。1、定义后缀式计算器的堆栈结构因为需要存储的单元不多，这里使用顺序栈，即用一维数组来模拟堆栈：#defineMAX100intstack[MAX]inttop=0因此程序中定义了长度为MAX的一维数组，这里MAX用宏定义为常数100，我们可以修改宏定义而重新定义堆栈的大小。整型数据top为栈顶指示，由于程序开始时堆栈中并无任何数据元素，因此top被初始化为0。2、存储后缀式计算器的运算数我们定义了堆栈stack[MAX]后，就可以利用入栈 *** 作存储先后输入的两个运算数。下面看一下是如何实现的：intpush(inti)/*存储运算数，入栈 *** 作*/{if(top#include#include#defineERR-1#defineMAX100/*定义堆栈的大小*/intstack[MAX]/*用一维数组定义堆栈*/inttop=0/*定义堆栈指示*/intpush(inti)/*存储运算数,入栈 *** 作*/{if(top#include#include#include#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2typedefintStatus#defineSTACK_INIT_SIZE100//初始分配量#defineSTACKINCREMENT10//存储空间的分配增量typedefcharElemTypetypedefElemTypeOperandType// *** 作数typedefcharOperatorTypetypedefstruct{ElemType*baseElemType*topintstacksize}SqStackStatusInitStack(SqStack&S){//构造一个空栈SS.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType))if(!S.base)exit(OVERFLOW)S.top=S.baseS.stacksize=STACK_INIT_SIZEreturnOK}StatusGetTop(SqStackS){ElemTypeeif(S.top==S.base)returnERRORe=*(S.top-1)returne}StatusPush(SqStack&S,ElemTypee){//插入元素e为新的栈顶元素if(S.top-S.base>=S.stacksize){S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType))if(!S.base)exit(OVERFLOW)S.top=S.base+S.stacksizeS.stacksize+=STACKINCREMENT}*S.top++=ereturnOK}StatusPop(SqStack&S,ElemType&e){//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERRORif(S.top==S.base)returnERRORe=*--S.topreturnOK}charIn(charc,charOP[]){if(c>=35&&c2'elseif(m[a][b]==2)return'47)a=atoi(&a)if(b>47)b=atoi(&b)switch(theta){case'+':returna+bbreakcase'-':returna-bbreakcase'*':returna*bbreakcase'/':returna/bbreak}}OperandTypeEvaluateExpression(){SqStackOPTR,OPNDOperandTypea,b,cOperatorTypethetaInitStack(OPTR)Push(OPTR,'#')InitStack(OPND)c=getchar()while(c!='#'||GetTop(OPTR)!='#'){if(!In(c,OP))elseswitch(Precede(GetTop(OPTR),c)){case'':Pop(OPTR,theta)Pop(OPND,b)Pop(OPND,a)Push(OPND,Operate(a,theta,b))break}}returnGetTop(OPND)}voidmain(){printf("(以#为结束符)\n")printf("请输入：\n")intaa=(int)EvaluateExpression()printf("%d",a)getch()}:ls都正确:C++InAction这本书里面有表达式求值的详细项目分析.:数据结构的书里面都有的,仔细看一下:studyall123的只能对0到9的数字运算才有效,对于10以上的数字就不行!不知道有没有更好的方法!:现在的人，连google一下都懒啊:实际上是按照逆波兰式的顺序让输入的表达式入栈，再根据运算符优先级来计算。:lenrning!

---