【求值】算符优先法对算术表达式求值

【求值】算符优先法对算术表达式求值

       算法用于实现算符优先，使用了两个栈，一个用于存放运算符，一个用于存放 *** 作数。算法中调用了InitStack函数构造空栈、GetTop函数返回栈顶元素、Pop函数删除栈顶元素、Push插入新的栈顶元素、Operate函数运算加减乘除、precede函数判断优先级、evaluateexpression函数用于实现算符优先。

#include
#include
#include
#include

#define STACK_INIT_SIZE 100
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define OPSETSIZE 7

char OPSET[OPSETSIZE]={'+','-','*','/','(',')','#'};
unsigned char prior[7][7] = {
{'>','>','<','<','<','>','>'},
{'>','>','<','<','<','>','>'},
{'>','>','>','>','<','>','>'},
{'>','>','>','>','<','>','>'},
{'<','<','<','<','<','=',' '},
{'<','<','<','<','<',' ','>'},
{'<','<','<','<','<',' ','='}};

typedef int Status;
typedef char SElemType;

typedef struct{
	SElemType *base;
	SElemType *top;
	int stacksize;
}SqStack;

Status InitStack(SqStack &S){
    S.base = (SElemType *)malloc(sizeof (SElemType)* STACK_INIT_SIZE);
    if (!S.base) exit (OVERFLOW);
    S.top = S.base;
    S.stacksize = STACK_INIT_SIZE;
    return OK;
}

SElemType GetTop(SqStack S) {
	if(S.top!=S.base) 
	return *(S.top-1);
}

Status Pop(SqStack &S,SElemType &e){
	if(S.top==S.base)
	return ERROR;
	e=*--S.top;
    return OK;
}

Status Push(SqStack &S,SElemType e){
	if(S.top-S.base==S.stacksize)
	return ERROR;
	*S.top++=e;
	return OK;
 } 

Status In(char c){
	if(c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c==')'||c=='#')return 1;
	else return 0;
}

Status Operate(SElemType a,SElemType theta,SElemType b){
	a=a-'0';b=b-'0';
	switch (theta){
    case '+': return a + b+'0';
    case '-': return a - b+'0';
    case '*': return a * b+'0';
    case '/': return a / b+'0';
     }
}

Status precede(char a,char b){   
    int i,j;
	 i = 0,j = 0;
	while(OPSET[i] != a)
     {  
          i++; 
     }
	while(OPSET[j] != b){ 
          j++;
     }
	return prior[i][j];
}

int evaluateexpression(){
	SqStack OPND,OPTR;
	char c,a,b,theta,x;
	InitStack(OPND); 
	InitStack(OPTR);
	Push(OPTR,'#');
	c=getchar();
	while(c!='#'||GetTop(OPTR)!='#'){
		if(!In(c)){
			Push(OPND,c);
			c=getchar();
          }
		else{ switch(precede(GetTop(OPTR),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;
              }
		} 
	}
	return GetTop(OPND)-'0';
}

int main(){
    printf("输入计算式，并以#结尾:n");
	printf("%dn",evaluateexpression());
	return 0;
}

       第一次输出结果中1+1计算为50，是未将字符型转为int型，在evaluateexpression函数最终的返回值中添加“ -‘0’  ”得以解决

运行截图： 

 算法流程图：