假设算术表达式满足:
(1) 小括号已匹配；
(2) 表达式无除0错误;
(3) 表达式中间没有多余的空格。
要求： 表达式计算的中间值可以是负数或者实数
【输入形式】第一行输入表达式字符串
【输出形式】第二行输出计算结果（保留两位小数）
【样例输入】(4+1*(5-2))-6/3
【样例输出】5.00
代码实现：
#include#include #define MAXSIZE 1024 #define TRUE 1 #define FALSE 0 typedef char ElemType; typedef struct {//队列结构定义 ElemType data[MAXSIZE]; int front; int rear; }SequenQueue; //初始化队列 SequenQueue* InitQueue() { SequenQueue* Q = NULL; Q = (SequenQueue*)malloc(sizeof(SequenQueue)); Q->front = Q->rear = 0; return Q; } //判断队列是否为空 int EmptyQueue(SequenQueue* Q) { if(Q->front == Q->rear) return TRUE; else return FALSE; } //判断队列是否满 int FullQueue(SequenQueue* Q) { if((Q->rear+1)%MAXSIZE==Q->front) return TRUE; else return FALSE; } //进队 int EnQueue(SequenQueue* Q, ElemType e) { if(FullQueue(Q)) return FALSE; Q->data[Q->rear] = e; Q->rear = (Q->rear+1)%MAXSIZE; return TRUE; } //出队 int DeQueue(SequenQueue* Q, ElemType *e) { if(EmptyQueue(Q)) return FALSE; else{ *e = Q->data[Q->front]; Q->front=(Q->front+1)%MAXSIZE; return TRUE; } } //取队头元素 ElemType GetHead(SequenQueue* Q) { return Q->data[Q->front]; } typedef struct { //顺序栈定义 ElemType data[MAXSIZE]; int top; //栈顶指针 }SequenStack; //初始化栈 SequenStack* InitStack( ) { SequenStack *S = (SequenStack*)malloc(sizeof(SequenStack)); S->top = -1; return S; } //判断栈是否为空 int EmptyStack(SequenStack *S) { if(-1 == S->top) return TRUE; else return FALSE; } //判断栈是否满 int FullStack(SequenStack *S) { if(S->top+1==MAXSIZE) return TRUE; else return FALSE; } //进栈 int Push(SequenStack *S, ElemType e) { //判断栈是否满 if(FullStack(S)) { printf("栈满！"); return FALSE; } //栈顶指针加1 //存值到栈顶 S->top++; S->data[S->top]=e; return TRUE; } //出栈 int Pop(SequenStack *S,char *e) { S->top--; *e=S->data[S->top+1]; return TRUE; } //取栈顶元素 ElemType GetTop(SequenStack *S) { return S->data[S->top]; } //给运算符优先级排序 // 优先级顺序：( < +, - < *, / int getPriority(char op) { int priority; if (op == '*' || op == '/') priority = 2; if (op == '+' || op == '-') priority = 1; if (op == '(') priority = 0; return priority; } int Trans(char *expr, SequenQueue *postfixQueue) { char *p = expr; ElemType e; SequenStack *signStack = NULL; //符号栈,它是辅助栈 //初始化符号栈 signStack = (SequenStack *)malloc (sizeof(SequenStack )); signStack->top = -1; //从左往右扫描表达式 while(*p != ' ') { if(*p >= '0' && *p <= '9') //数字直接入表达式队列 { EnQueue(postfixQueue, *p); } else if('(' == *p) //左括号，直接入符号栈 { Push(signStack,*p); } else if(')' == *p) //如果是右括号，则将左括号前的所有符号出栈，并入表达式队列 { do{ Pop(signStack, &e); //符号出栈 if(e != '(') //将非(入表达式队列 EnQueue(postfixQueue,e); }while((e != '(') && (!EmptyStack(signStack))); } else //其他符号，根据优先级选择进栈 { if(EmptyStack(signStack)) //如果符号栈为空，则直接将当前运算符入栈 { Push(signStack, *p); } else { while(getPriority(*p) <= getPriority(GetTop(signStack) )) //比较当前运算符与栈顶的优先级 { Pop(signStack, &e); //符号出栈 EnQueue(postfixQueue, e); //运算符入表达式队列 if(EmptyStack(signStack)) //判断符号栈是否为空 { break; } } //将当前运算符入栈 Push(signStack,*p); } }//end else p++; }//end while //将符号栈全部入表达式队列 while(!EmptyStack(signStack)) { Pop(signStack, &e); EnQueue(postfixQueue, e); } return TRUE; } double calculate(SequenQueue* postfixQueue){ double a[100],S=0; ElemType e; int i = -1; while(!EmptyQueue(postfixQueue)) { DeQueue(postfixQueue, &e); if(e<='9'&&e>='0'){ i++; a[i]=(double)(e-'0'); } switch(e){ case'+':S = a[i-1]+a[i];i--;a[i]=S;break; case'-':S = a[i-1]-a[i];i--;a[i]=S;break; case'*':S = a[i-1]*a[i];i--;a[i]=S;break; case'/':S = a[i-1]/a[i];i--;a[i]=S;break; } } return S; } int main(int argc, char *argv[]) { SequenQueue *postfixQueue = NULL; //表达式队列 char expression[100]; //输入计算表达式 gets(expression); postfixQueue = InitQueue(); //初始化后缀表达式队列 Trans(expression, postfixQueue); printf("%.2fn", calculate( postfixQueue)); return 0; }
