C语言实现表达式求值

#include <stdio.h> #include <string.h> #include <stdlib.h> #include <math.h> #include <conio.h> #define TRUE 1 #define FALSE 0 #define Stack_Size 50 char ops[7]={'+','-','*','/','(',')','#'}; /*运算符数组*/ int cmp[7][7]={{2,2,1,1,1,2,2}, /*用来进行比较运算符优先级的矩阵,3代表'=',2代表'>',1代表'<',0代表不可比*/ {2,2,1,1,1,2,2}, {2,2,2,2,1,2,2}, {2,2,2,2,1,2,2}, {1,1,1,1,1,3,0}, {2,2,2,2,0,2,2}, {1,1,1,1,1,0,3}}; typedef struct { char elem[Stack_Size]; int top; }SeqStack; /*运算符栈的定义*/ typedef struct { int elem[Stack_Size]; int top; }nSeqStack; /* 运算数栈的定义*/ void InitStack(SeqStack *S) /*初始化运算符栈*/ { S->top =-1; } void InitStackn(nSeqStack *S) /*初始化运算数栈*/ { S->top =-1; } int IsEmpty(SeqStack *S) /*判断栈S为空栈时返回值为真，反之为假*/ { return(S->top==-1?TRUE:FALSE); } int IsEmptyn(nSeqStack *S) /*判断栈S为空栈时返回值为真，反之为假*/ { return(S->top==-1?TRUE:FALSE); } /*判栈满*/ int IsFull(SeqStack *S) /*判断栈S为满栈时返回值为真，反之为假*/ { return(S->top==Stack_Size-1?TRUE:FALSE); } int IsFulln(nSeqStack *S) /*判断栈S为满栈时返回值为真，反之为假*/ { return(S->top==Stack_Size-1?TRUE:FALSE); } int Push(SeqStack *S, char x) /*运算符栈入栈函数*/ { if (S->top==Stack_Size-1) { printf("Stack is full!\n"); return FALSE; } else { S->top++; S->elem[S->top]=x; return TRUE; } } int Pushn(nSeqStack *S, int x) /*运算数栈入栈函数*/ { if (S->top==Stack_Size-1) { printf("Stack is full!\n"); return FALSE; } else { S->top++; S->elem[S->top]=x; return TRUE; } } int Pop(SeqStack *S, char *x) /*运算符栈出栈函数*/ { if (S->top==-1) { printf("运算符栈空!\n"); return FALSE; } else { *x=S->elem[S->top]; S->top--; return TRUE; } } int Popn(nSeqStack *S, int *x) /*运算数栈出栈函数*/ { if (S->top==-1) { printf("运算符栈空!\n"); return FALSE; } else { *x=S->elem[S->top]; S->top--; return TRUE; } } char GetTop(SeqStack *S) /*运算符栈取栈顶元素函数*/ { if (S->top ==-1) { printf("运算符栈为空!\n"); return FALSE; } else { return (S->elem[S->top]); } } int GetTopn(nSeqStack *S) /*运算数栈取栈顶元素函数*/ { if (S->top ==-1) { printf("运算符栈为空!\n"); return FALSE; } else { return (S->elem[S->top]); } } int Isoperator(char ch) /*判断输入字符是否为运算符函数,是返回TRUE,不是返回FALSE*/ { int i; for (i=0;i<7;i++) { if(ch==ops[i]) return TRUE; } return FALSE; } /* int isvariable(char ch) { if (ch>='a'&&ch<='z') return true; else return false; }*/ char Compare(char ch1, char ch2) /*比较运算符优先级函数*/ { int i,m,n; char pri; int priority; for(i=0;i<7;i++) /*找到相比较的两个运算符在比较矩阵里的相对位置*/ { if(ch1==ops[i]) m=i; if (ch2==ops[i]) n=i; } priority = cmp[m][n]; switch(priority) { case 1: pri='<'; break; case 2: pri='>'; break; case 3: pri='='; break; case 0: pri='$'; printf("表达式错误!\n"); break; } return pri; } int Execute(int a, char op, int b) /*运算函数*/ { int result; switch(op) { case '+': result=a+b; break; case '-': result=a-b; break; case '*': result=a*b; break; case '/': result=a/b; break; } return result; } int ExpEvaluation() /*读入一个简单算术表达式并计算其值。optr和operand分别为运算符栈和运算数栈，OPS为运算符集合*/ { int a,b,v,temp; char ch,op; char *str; int i=0; SeqStack optr; nSeqStack operand; InitStack(&optr); InitStackn(&operand); Push(&optr,'#'); printf("请输入表达式(以#结束):\n"); /*表达式输入*/ str =(char *)malloc(50*sizeof(char)); gets(str); ch=str[i]; i++; while(ch!='#'||GetTop(&optr)!='#') { if(!Isoperator(ch)) { temp=ch-'0'; /*将字符转换为十进制数*/ ch=str[i]; i++; while(!Isoperator(ch)) { temp=temp*10 + ch-'0'; /*将逐个读入运算数的各位转化为十进制数*/ ch=str[i]; i++; } Pushn(&operand,temp); } else { switch(Compare(GetTop(&optr),ch)) { case '<': Push(&optr,ch); ch=str[i]; i++; break; case '=': Pop(&optr,&op); ch=str[i]; i++; break; case '>': Pop(&optr,&op); Popn(&operand,&b); Popn(&operand,&a); v=Execute(a,op,b); /* 对a和b进行op运算 */ Pushn(&operand,v); break; } } } v=GetTopn(&operand); return v; } void main() /*主函数*/ { int result; result=ExpEvaluation(); printf("\n表达式结果是%d\n",result); }