Question

C语言表达式求值

RT
C或C++语言实现输入一个完整表达式，然后求值

除了使用数据结构的堆栈应用，能不能有其他方法实现这一功能？

Answer 1

//表达式求值
//By:jimly
//10/10/2009
//例如：输入2+2（4-6*3）=
//以"="结束,然后回车即出结果
#include <stdio.h>
#include <conio.h>
#include <windows.h>
#include <assert.h>
typedef float ElemType;
typedef struct Stack
{
ElemType *base; // 栈基址
ElemType *top; // 栈顶
int stacksize; // 栈存储空间的尺寸
} SqStack;
/*------------------------------------------------------------
// 栈的基本操作
------------------------------------------------------------*/
bool InitStack(SqStack *S);
bool InitStack(SqStack *S);
void DestroyStack(SqStack *S);
bool StackEmpty(SqStack S);
int StackLength(SqStack S);
ElemType GetTop(SqStack S, ElemType *e);
void StackTraverse(SqStack S, void (*fp)(ElemType));
bool Push(SqStack *S, ElemType e);
bool Pop(SqStack *S, ElemType *e);
/*------------------------------------------------------------
// 表达式求值的操作函数定义
------------------------------------------------------------*/
char Precede(char A1,char A2);
ElemType Operate(ElemType a,ElemType theta,ElemType b);
bool In(char c,char op[]);
ElemType EvaluateExpression();
void Menu();//////////////////////////////////////////////
// Eval_exdivssion.cpp 表达式求值实现函数 //
//////////////////////////////////////////////
/*------------------------------------------------------------
操作目的： 判定运算符栈的栈顶运算符A1和读入的运算符A2之间优先关系的函数
初始条件： 无
操作结果： 判断出优先关系
函数参数：
char A1 运算符
char A2 运算符
返回值：
char 大小关系
------------------------------------------------------------*/
char Precede(char A1,char A2)
{
if (A1 == '+' || A1 == '-')
{
if (A2 == '+' || A2 == '-' || A2 == ')' || A2 == '=')
{
return '>';
}
else
return '<';
}
if (A1 == '*' || A1 == '/')
{
if (A2 == '(')
{
return '<';
}
else
return '>';
}
if (A1 == '(')
{
if (A2 == ')')
{
return '=';
}
if (A2 == '=')
{
return 'E';
}
else
return '<';
}
if (A1 == ')')
{
if (A2 == '(')
{
return 'E';
}
if (A2 == '=')
{
return 'E';
}
else
return '>';
}
if (A1 == '=')
{
if (A2 == '=')
{
return '=';
}
else
return '<';
}
else
return '=';
}
/*------------------------------------------------------------
操作目的： 二元运算a与b的函数
初始条件： 无
操作结果： 返回运算结果
函数参数：
ElemType a 操作数
ElemType theta 操作符
ElemType b 操作数
返回值：
ElemType 运算结果
------------------------------------------------------------*/
ElemType Operate(ElemType a,ElemType theta,ElemType b)
{
switch(char(theta))
{
case '+':
return a += b;
break;
case '-':
return a -= b;
break;
case '*':
return a *= b;
break;
case '/':
if(b==0)
{
printf("除数不能为0！！\n");
exit(0);
}
return a /= b;
break;
} return 0;
}
/*------------------------------------------------------------
操作目的： 判断字符c是否属于运算符集合op
初始条件： 无
操作结果： 返回判断结果
函数参数：
char c 要判断的字符
char op[] 运算符集合
返回值：
bool 属于返回true 否则返回false
------------------------------------------------------------*/
bool In(char c,char op[])
{
for (int i = 0;i<7;i++)
{
if (op[i] == c)
return true;
}
return false;
}
/*------------------------------------------------------------
操作目的： 算术表达式求值的运算符优先算法
初始条件： 无
操作结果： 返回表达式的值
函数参数：
无
返回值：
ElemType 运算结果
------------------------------------------------------------*/
ElemType EvaluateExpression()
{
SqStack OPTR; //运算符栈
SqStack OPND; //运算数栈
char Ct = '='; //判断是否结束的标识
int i = 0,j = 1;
ElemType e = 0,t = 0,c;
char op[7] = {'+','-','*','/','(',')','='}; InitStack(&OPTR); //初始化
Push(&OPTR,Ct);
InitStack(&OPND); //初始化 c = (float)getchar();
while (c!='=' || GetTop(OPTR,&e)!='=')
{
if (!In((char)c,op)) //不是运算e符进栈
{
while(!In((char)c,op)) //可以是几位数
{
t = t*10+(c-48);
c = (float)getchar();
}
Push(&OPND,t);
t = 0;
} else
{
switch (Precede((char)GetTop(OPTR,&e),(char)c))
{
case '<'://栈顶元素优先权低
Push(&OPTR,c);
c = (float)getchar();
break;
case '='://脱括号并接受下个字符
ElemType x;
Pop(&OPTR,&x);
c = (float)getchar();
break;
case '>'://退栈并将运算结果入栈
ElemType b,theta,a;
Pop(&OPTR,&theta);
Pop(&OPND,&b);
Pop(&OPND,&a);
Push(&OPND,Operate(a,theta,b));
break;
case 'E':
printf("括号不匹配！！\n");
exit(0);
break;

}
}
}
ElemType tem = GetTop(OPND,&e);
DestroyStack(&OPND);
DestroyStack(&OPTR);
return tem;
}/***
*DynaSeqStack.cpp - 动态顺序栈，即栈的动态顺序存储实现
****/
const int STACK_INIT_SIZE = 100; // 初始分配的长度
const int STACKINCREMENT = 10; // 分配内存的增量
/*------------------------------------------------------------
操作目的： 初始化栈
初始条件： 无
操作结果： 构造一个空的栈
函数参数：
SqStack *S 待初始化的栈
返回值：
bool 操作是否成功
------------------------------------------------------------*/
bool InitStack(SqStack *S)
{
assert(S != NULL);
S->base = (ElemType *)malloc(sizeof(ElemType) * STACK_INIT_SIZE);

if(S->base == NULL) return false; S->top = S->base;
S->stacksize = STACK_INIT_SIZE; return true;
}/*------------------------------------------------------------
操作目的： 销毁栈
初始条件： 栈S已存在
操作结果： 销毁栈S
函数参数：
SqStack *S 待销毁的栈
返回值：
无
------------------------------------------------------------*/
void DestroyStack(SqStack *S)
{
assert(S != NULL); free(S->base);
S->top = S->base = NULL;
}/*------------------------------------------------------------
操作目的： 判断栈是否为空
初始条件： 栈S已存在
操作结果： 若S为空栈，则返回true，否则返回false
函数参数：
SqStack S 待判断的栈
返回值：
bool 是否为空
------------------------------------------------------------*/
bool StackEmpty(SqStack S)
{
assert((S.base != NULL) && (S.top != NULL));
return(S.base == S.top);
}/*------------------------------------------------------------
操作目的： 得到栈的长度
初始条件： 栈S已存在
操作结果： 返回S中数据元素的个数
函数参数：
SqStack S 栈S
返回值：
int 数据元素的个数
------------------------------------------------------------*/
int StackLength(SqStack S)
{
assert((S.base != NULL) && (S.top != NULL));
return(S.top-S.base);
}/*------------------------------------------------------------
操作目的： 得到栈顶元素
初始条件： 栈S已存在
操作结果： 用e返回栈顶元素
函数参数：
SqStack S 栈S
ElemType *e 栈顶元素的值
返回值：
bool 操作是否成功
------------------------------------------------------------*/
ElemType GetTop(SqStack S, ElemType *e)
{
assert((S.base != NULL) && (S.top != NULL));
if(StackEmpty(S)) return false; *e = *(S.top-1);
return *e;
}/*------------------------------------------------------------
操作目的： 遍历栈
初始条件： 栈S已存在
操作结果： 依次对S的每个元素调用函数fp
函数参数：
SqStack S 栈S
void (*fp)() 访问每个数据元素的函数指针
返回值：
无
------------------------------------------------------------*/
void StackTraverse(SqStack S, void (*fp)(ElemType))
{
assert((S.base != NULL) && (S.top != NULL));
for(; S.base<S.top; S.base++) (*fp)(*S.base);
}/*------------------------------------------------------------
操作目的： 压栈——插入元素e为新的栈顶元素
初始条件： 栈S已存在
操作结果： 插入数据元素e作为新的栈顶
函数参数：
SqStack *S 栈S
ElemType e 待插入的数据元素
返回值：
bool 操作是否成功
------------------------------------------------------------*/
bool Push(SqStack *S, ElemType e)
{
if (S->top - S->base>=S->stacksize)
{
S->base = (ElemType *)realloc(S->base,(S->stacksize + STACKINCREMENT) * sizeof(ElemType));
if (!S->base)
exit(0);
S->top = S->base + S->stacksize;
S->stacksize += STACKINCREMENT;
}
*S->top++ = e; return true;
}/*------------------------------------------------------------
操作目的： 弹栈——删除栈顶元素
初始条件： 栈S已存在且非空
操作结果： 删除S的栈顶元素，并用e返回其值
函数参数：
SqStack *S 栈S
ElemType *e 被删除的数据元素值
返回值：
bool 操作是否成功
------------------------------------------------------------*/
bool Pop(SqStack *S, ElemType *e)
{
if(S == NULL) return false;
assert((S->base != NULL) && (S->top != NULL));
if(StackEmpty(*S)) return false; *e = *(--S->top);
return true;
}//////菜单///////
void Menu()
{
printf("表达式求值模拟程序\n\n");

printf("功能菜单：\n");
printf("==============\n");
printf("[1] 输入表达式并求值\n");
printf("[0] 退出 \n");
printf("==============\n");
printf("请输入你的选择(0~1)（以回车结束）：");
}///////// 主函数 ///////////
//////////////////////////////
int main()
{
char ch = ' ',tp; do
{
system("cls");
Menu();
ch = getchar();
if (ch == '0')
break;
tp = getchar();
printf("请输入一个表达式（最后输入”=“,然后回车出结果）：");
printf("这个表达式结果为：%g\n",EvaluateExpression());
tp = getchar();
printf("任意键继续...");
getch();
} while (true); return 0;
}//end

Answer 2

按1输入表达式（不用输入＝号）
按2计算
按3输出结果
按4退出

程序如下：

#include<stdio.h>
#include <string.h>
#include <conio.h>

#define PLUS 0
#define MINUS 1
#define POWER 2
#define DIVIDE 3
#define LEFTP 4
#define RIGHP 5
#define STARTEND 6
#define DIGIT 7
#define POINT 8

#define NUM 7
#define NO 32767
#define STACKSIZE 20
char a[]={'+','-','*','/','(',')','#'};
int j,PriorityTable[7][7]={{ 1, 1,-1,-1,-1, 1, 1},
{ 1, 1,-1,-1,-1, 1, 1},
{ 1, 1, 1, 1,-1, 1, 1},
{ 1, 1, 1, 1,-1, 1, 1},
{-1,-1,-1,-1,-1, 0, NO},
{ 1, 1, 1, 1,NO, 1, 1},
{-1,-1,-1,-1,-1,NO, 0}
};
int menu(void);
void
InputExpression(char str[])
{ int len;
printf("Input expression string:\n");
scanf("%s",str);
len=strlen(str);
str[len]='#';
str[len+1]='\0';
}
int GetCharType(char ch)
{ int i;
for(i=0;i<NUM;i++) if(ch==a[i]) return(i);
if(ch>='0' && ch<='9') return(DIGIT);
if(ch=='.') return(POINT);
return(-1);
}
int EXCUTE(char *str,double *Result)
{
int pp,strlength,topTr,topNd,CharType,OPTR[STACKSIZE],a;
double number,temp,OPND[STACKSIZE];

OPTR[0]=STARTEND;
topTr=1;
topNd=0;
pp=0;
while((str[pp]))
{ CharType=GetCharType(str[pp]);
switch(CharType)
{ case -1:
return(0);
case DIGIT:
number=0;
while

(str[pp]>='0' && str[pp]<='9')
{ number=number*10+(str[pp]-48);
pp++;
}
if(str[pp]=='.')
{ temp=10.0;
pp++;
while(str[pp]>='0' && str[pp]<='9')
{ number=number+(str[pp]-48)/temp;
temp=temp*10;
pp++;
}
}
OPND[topNd]=number;
topNd++;
break;
case POINT:
number=0;
temp=10.0;
pp++;
while(str[pp]>='0' && str[pp]<='9')
{ number=number+(str[pp]-48)/temp;
temp=temp*10;
pp++;
}
OPND[topNd]=number;printf("%lf",number);
topNd++;
break;

case PLUS:
case MINUS:
case POWER:
case DIVIDE:

{int i;<br> i=PriorityTable[OPTR[topTr-1]][CharType];<br> if(i==-1)<br> {OPTR[topTr]=CharType;<br> topTr++;<br> }
if(i==1)
{while(i==1)<br> {<br> j=OPTR[topTr-1];<br> if(j==0)OPND[topNd-2]=OPND[topNd-2]+OPND[topNd-1];<br> if(j==1)OPND[topNd-2]=OPND[topNd-2]-OPND[topNd-1];<br> if(j==2)OPND[topNd-2]=OPND[topNd-2]*OPND[topNd-1];<br> if(j==3)OPND[topNd-2]=OPND[topNd-2]/OPND[topNd-1];<br> topNd--;<br> topTr--;<br> i=PriorityTable[OPTR[topTr-1]][CharType];<br> }
OPTR[topTr]=CharType;topTr++;
}
pp++;break;
}
case LEFTP:
{

OPTR[topTr]=LEFTP;
topTr++;pp++;
break;
}

case RIGHP:
{ while(1)
if(OPTR[topTr-1]==LEFTP){topTr--;pp++;break;}
else if(OPTR[topTr-1]==STARTEND)return(0);
else
{j=OPTR[topTr-1];<br> if(j==0)OPND[topNd-2]=OPND[topNd-2]+OPND[topNd-1];<br> else if(j==1)OPND[topNd-2]=OPND[topNd-2]-OPND[topNd-1];<br> else if(j==2)OPND[topNd-2]=OPND[topNd-2]*OPND[topNd-1];<br> else if(j==3)OPND[topNd-2]=OPND[topNd-2]/OPND[topNd-1];<br> topNd--;<br> topTr--;<br> }
break;
}

case STARTEND:

while(OPTR[topTr-1]!=STARTEND)
{
j=OPTR[topTr-1];
if(j==0)OPND[topNd-2]=OPND[topNd-2]+OPND[topNd-1];
else if(j==1)OPND[topNd-2]=OPND[topNd-2]-OPND[topNd-1];
else if(j==2)OPND[topNd-2]=OPND[topNd-2]*OPND[topNd-1];
else if(j==3)OPND[topNd-2]=OPND[topNd-2]/OPND[topNd-1];
topNd--;
topTr--;
}

if(topNd==1)
{ *Result=OPND[0];return(1);
}
else return(0);
}

}
return(1
);
}
void main()
{ int num,flag;
double result;
char str[256];
str[0]=0;
while(1)
{ num=menu();
switch(num)
{
case 1:
InputExpression(str);
flag=0;
printf("%s\n",str);
getchar();
getchar();
break;

case 2:
if(str[0]==0)
{ printf("Expresson is Empty!");
getchar();
break;
}
if(!EXCUTE(str,&result))
{ printf("The expression has error!\n");
getchar();
}
else
{ printf("calulation has finished!\n");
getchar();
flag=1;
}
break;
case 3:
if(flag)
{ printf("#%s=%lf\n",str,result);
getchar();
getchar();
}
break;
case 4:
break;
}
if(num==4) break;
}
}
int menu(void)
{ int num;
clrscr();
printf("%20c1--input expression\n",' ');
printf("%20c2--calculation expression\n",' ');
printf("%20c3--print result\n",' ');
printf("%20c4--Quit\n",' ');
printf(" please select 1,2,3,4:");
do{
scanf("%d",&num);
}while(num<1 || num>4);
return(num);
}

Answer 3

实现表达式求值我是先将中缀表达式转换为后缀表达式，然后用堆栈实现求值的，至于其他方法还没想过呢，期待有更好的方法吧。