C语言表达式求值(链栈)-创新互联

该代码仅适用于个位数 (整型) 表达式求值(即表达式中进行运算的都是个位数，并且每次运算的结果也是个位数)

运行过程及结果 

1.首先需要有

两个链栈，分别存储表达式中的 运算数【 OPND 】和 运算符【 OPTR 】，既然分为两个栈存储，当然还需要可以判定读入字符的是否为运算符或者运算数的函数【 In() 】 

bool In(char ch){
	if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(' || ch == ')' || ch == '#'){
		return true;
	}else{
		return false;
	}
}

2.有了存储表达式的栈，下一步就要完成表达式的运算：

  i.需要一个可以判断运算符之间优先级的函数【 Precede() 】

char Precede(char a, char b){
	if (a == '+' || a == '-'){
		if (b == '+' || b == '-' || b == ')' || b == '#'){
			return '>';
		}else{
			return '<';
		}
	}else if (a == '*' || a == '/'){
		if (b == '+' || b == '-' || b == '*' || b == '/' || b == ')' || b == '#'){
			return '>';
		}else{
			return '<';
		}
	}else if (a == '('){
		if (b == ')'){
			return '=';
		}else if (b == '#'){					//表达式错误
			return '?';
		}else{
			return '<';
		}
	}else if (a == '#'){
		if (b == '#'){
			return '=';
		}else if (b == ')'){					//表达式错误
			return '?';
		}else {
			return '<';
		}
	}
}

其实这个函数还可以根据运算符优先级关系图定于成一个二维数组，直接返回两个运算符的优先级大小，如下：

int change(char ch){
	if (ch == '+'){
		return 0;
	}else if (ch == '-'){
		return 1;
	}else if (ch == '*'){
		return 2;
	}else if (ch == '/'){
		return 3;
	}else if (ch == '('){
		return 4;
	}else if (ch == ')'){
		return 5;
	}else if (ch == '#'){
		return 6;
	}
}

char Precede(char a, char b){
	int A = change(a);
	int B = change(b);
    char judge[7][7] = {
    	{'>','>','<','<','<','>','>'},
    	{'>','>','<','<','<','>','>'},
    	{'>','>','>','>','<','>','>'},
    	{'>','>','>','>','<','>','>'},
    	{'<','<','<','<','<','=','?'},
    	{'>','>','>','>','?','>','>'},
    	{'<','<','<','<','<','?','='}
	};
	return judge[A][B];
}

感觉这个判断方法更加清晰易懂 ，比用 if 更加简练一些

  ii.还需要可以对运算数进行运算的函数【 Operate() 】

char Operate(char a, char theta, char b){
	int A = a - 48;
	int B = b - 48;
	int C;
	if (theta == '+'){
		C = A + B ;
	}else if (theta == '-'){
		C = A - B ;
	}else if (theta == '*'){
		C = A * B ;
	}else if (theta == '/'){
		C = A / B ;
	}
	return C + '0';
}

将字符数字 (仅限个位数字) 转化成整型减去48即可，将字符转化成整型会直接转换成其ASCII表中对应的十进制数，对应减去48就可以了，最后整型数字 (也仅限于个位数字) 转化成字符加上'0'就可以了，系统会自动转化

3.最重要的一步就是根据以上条件编写一个可以实现表达式求解的算法函数【EvaluateExpression() 】

void EvaluateExpression(){
	LinkStack OPTR,OPND;
	OPTR = (LinkStack)malloc(sizeof(LinkStack));            //创建OPND栈(存放运算数)
	OPND = (LinkStack)malloc(sizeof(LinkStack));            //创建OPTR栈(存放运算符)
	InitStack(&OPTR);
	InitStack(&OPND);
	Push(&OPTR, '#');                                       //将表达式起始符'#'压入OPTR中
	char ch;
	scanf("%c", &ch);
	while(ch != '#' || GetTop(OPTR) != '#'){                
		if (!In(ch)){                                       //判断输入的是否是运算符
			Push(&OPND, ch);
			scanf("%c", &ch);
		}else{
			switch(Precede(GetTop(OPTR), ch)){             //比较OPTR的栈顶元素和ch的优先级
				case '<':                                  //运算符ch优先级高，继续压入
					Push(&OPTR,ch);
					scanf("%c", &ch);
					break;
				case '>':                                  //OPTR栈顶元素优先级高，弹出运算
					char theta,a,b;
					Pop(&OPTR,&theta);
					Pop(&OPND,&b);
					Pop(&OPND,&a);
					Push(&OPND,Operate(a,theta,b));        //进行运算，并将结果压入OPND
					break;
				case '=':                                  //OPTR栈顶元素为'('，ch也为')'
					char temp;                             //不会出现都为'#'的情况
					Pop(&OPTR,&temp);                       
					scanf("%c", &ch);
					break;
				case '?':
					printf("表达式错误！");
					return;
			}
		}
	}
	printf("表达式的结果为：%c", GetTop(OPND));
}

完整代码

#include#includetypedef struct StackNode{
	char data;
	StackNode *next;
}*LinkStack;

void InitStack(LinkStack *S){
	*S = NULL;
}

void Pop(LinkStack *S, char *ch){
	*ch = (*S)->data;
	*S = (*S)->next;
}

void Push(LinkStack *S, char ch){
	LinkStack node = (LinkStack)malloc(sizeof(LinkStack));
	node->data = ch;
	node->next = *S;
	*S = node;
}

char GetTop(LinkStack S){
	return S->data;
}

bool In(char ch){
	if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(' || ch == ')' || ch == '#'){
		return true;
	}else{
		return false;
	}
}

char Precede(char a, char b){
	if (a == '+' || a == '-'){
		if (b == '+' || b == '-' || b == ')' || b == '#'){
			return '>';
		}else{
			return '<';
		}
	}else if (a == '*' || a == '/'){
		if (b == '+' || b == '-' || b == '*' || b == '/' || b == ')' || b == '#'){
			return '>';
		}else{
			return '<';
		}
	}else if (a == '('){
		if (b == ')'){
			return '=';
		}else if (b == '#'){					//表达式错误
			return '?';
		}else{
			return '<';
		}
	}else if (a == '#'){
		if (b == '#'){
			return '=';
		}else if (b == ')'){					//表达式错误
			return '?';
		}else {
			return '<';
		}
	}
}

char Operate(char a, char theta, char b){
	int A = a - 48;
	int B = b - 48;
	int C;
	if (theta == '+'){
		C = A + B ;
	}else if (theta == '-'){
		C = A - B ;
	}else if (theta == '*'){
		C = A * B ;
	}else if (theta == '/'){
		C = A / B ;
	}
	return C + '0';
}

void EvaluateExpression(){
	LinkStack OPTR,OPND;
	OPTR = (LinkStack)malloc(sizeof(LinkStack));
	OPND = (LinkStack)malloc(sizeof(LinkStack));
	InitStack(&OPTR);
	InitStack(&OPND);
	Push(&OPTR, '#');
	char ch;
	scanf("%c", &ch);
	while(ch != '#' || GetTop(OPTR) != '#'){
		if (!In(ch)){
			Push(&OPND, ch);
			scanf("%c", &ch);
		}else{
			switch(Precede(GetTop(OPTR), ch)){
				case '<':
					Push(&OPTR,ch);
					scanf("%c", &ch);
					break;
				case '>':
					char theta,a,b;
					Pop(&OPTR,&theta);
					Pop(&OPND,&b);
					Pop(&OPND,&a);
					Push(&OPND,Operate(a,theta,b));
					break;
				case '=':
					char temp;
					Pop(&OPTR,&temp);
					scanf("%c", &ch);
					break;
				case '?':
					printf("表达式错误！");
					return;
			}
		}
	}
	printf("表达式的结果为：%c", GetTop(OPND));
}

int main(){
	printf("请输入一个表达式(以#结束)：");
	EvaluateExpression();
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧