[C++知识库]C语言-用栈实现表达式求值

目录

目的描述：

算法的基本思想：

错误点：

完整代码：

1.输入输出

2.栈操作函数包（数组堆栈.h）

3.实现表达式求值函数包（表达式求值.c）

4.测试输出：

目的描述：

算符优先算法要实现的是，根据运算优先关系来对一个表达式求值，假如说要计算：

4+2*3-10/5

运算的顺序例如：

4+2*3-10/5? =? 4+6-10/5? =? 10-10/5? =? 10-2? =? 8 (开始不是很理解的话可以继续往下看）

算法的基本思想：

为实现算符优先算法，可以使用两个工作栈。一个称做?OPTR，用以寄存运算符；另一个称做?OPND，用以寄存操作数或运算结果。

（1）首先置操作数栈为空栈，表达式起始符“＃”为运算符栈的栈底元素；
（2） 依次读人表达式中每个字符，若是操作数则进?OPND栈，若是运算符则和OPTR?栈的栈顶运算符比较优先权后作相应操作，直至整个表达式求值完毕(即?OPTR栈的栈顶元素和当前读人的字符均为“＃”)

（3）在这里分别定义了两套对栈进行基本操作的函数，只有函数名改变其他均相同。这样做的原因是，在对寄存运算符时，需要字符栈；而寄存操作数或运算结果时，字符栈无法满足多位数的操作，所以这里采用数字栈（后来看到了另一位作者的文章，两个栈都采用数字栈也可以实现，并且会大大减少代码数量，原理就是在存放操作符的时候，将会转化成ASCII码的形式存入栈中）

（4）这里是两个最近的运算符的优先级关系表：（用来参考着写计算算符优先级的函数）

?（空白的地方是不可能存在的合法运算符关系，可忽略）

（5）通过利用对栈的基本操作函数，对两个栈进行操作，按步骤分解可以参考下表

?

错误点：

（记录一下自己遇到的错误）

（1）就是关于在寄存操作数或运算结果时开始没有考虑到有多位数的情况，我对多位数的处理是，设定了一个flag判断，如果连续getchar()得到的都是数字，就令flag=1；如果遇到了运算符，就令flag=0。

（2）在计算每一步结果的函数 Operate(double a, char theta, double b)里，当这是的操作是’-‘或者’/‘时，要注意a，b的顺序，因为栈的特点是LIFO（last in first out），所以除数和被除数，减数和被减数就会颠倒过来，要记得写成反的。

（3）记得判断输入getchar()为换行符’\n'时要跳出循环的判断。

完整代码：

1.输入输出

输入：一个只含有‘+’，‘-’，‘/’，‘*’，‘#’运算符和数字的运算表达式，中间没有空格，结尾以#结束

输出：一个整数计算结果

2.栈操作函数包（数组堆栈.h）

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef char Elemtype1;//提供给存储运算符的栈使用
typedef double Elemtype2;//提供给存储操作数的栈使用

typedef struct {
	Elemtype1 *data;
	int top;//栈顶指针，这里用int类型表示指针的下标
	int stacksize;
} SqStack1;
Elemtype1 Pop1(SqStack1 *s);

typedef struct {
	Elemtype2 *data;
	int top;//栈顶指针，这里用int类型表示指针的下标
	int stacksize;
} SqStack2;
Elemtype2 Pop2(SqStack2 *s);

SqStack1 InitStack1() {//空栈构造函数
	SqStack1 s;
	s.data = (Elemtype1 *)malloc(STACK_INIT_SIZE * sizeof(Elemtype1));
	s.top = -1; //表示栈空
	s.stacksize = STACK_INIT_SIZE;
	if (s.data != NULL)
	{}
	else
		printf("Init error!\n");
	return s;
}

void DestroyStack1(SqStack1 *s) {//销毁栈函数
	free(s->data);
}

int StackEmpty1(SqStack1 *s) {//判断是否为空栈,是返回1，否 返回0
	if (s->top == -1)
		return 1;
	else
		return 0;
}

void ClearStack1(SqStack1 *s) {//清除栈
	while (StackEmpty1(s) != 1) {
		Pop1(s);
	}
}

void Push1(SqStack1 *s, Elemtype1 e) {//添加元素入栈
	if (s->top >= s->stacksize) {
		s->data = (Elemtype1 *)malloc((STACK_INIT_SIZE + STACKINCREMENT) * sizeof(Elemtype1));
		s->stacksize += STACKINCREMENT;
		if (s->data != NULL) {}
		else
			printf("Push error!\n");
	} else {
		s->top++;
		s->data[s->top] = e;
	}
}

Elemtype1 Pop1(SqStack1 *s) {//删除栈顶元素并返回其值，否则返回ERROR
	if (StackEmpty1(s) != 1 && s->top >= 0) {
		Elemtype1 e = s->data[s->top];
		s->top--;
		return e;
	}
	printf("Pop error!\n");
}

int StackLength1(SqStack1 *s) {//返回栈的长度
	int len = 0, temp = s->top;
	while (temp >= 0) {
		len++;
		temp--;
	}
	return len;
}

Elemtype1 GetTop1(SqStack1 *s) {//返回栈顶元素
	if (StackEmpty1(s) != 1) {
		return s->data[s->top];
	} else
		printf("GetTop error!\n");
}

int StackTraverse1(SqStack1 *s) {//从栈底向栈顶访问每个元素
	if (StackEmpty1(s) == 1) {
		printf("栈为空！\n");
		return 0;
	}
	int temp = 0;
	while (temp <= s->top) {
		printf("%c ", s->data[temp]);
		temp++;
	}
	return 1;
}

//以下是对第二组堆栈操作的定义*************************************************
SqStack2 InitStack2() {//空栈构造函数
	SqStack2 s;
	s.data = (Elemtype2 *)malloc(STACK_INIT_SIZE * sizeof(Elemtype2));
	s.top = -1; //表示栈空
	s.stacksize = STACK_INIT_SIZE;
	if (s.data != NULL)
	{}
	else
		printf("Init error!\n");
	return s;
}

void DestroyStack2(SqStack2 *s) {//销毁栈函数
	free(s->data);
}

int StackEmpty2(SqStack2 *s) {//判断是否为空栈,是返回1，否 返回0
	if (s->top == -1)
		return 1;
	else
		return 0;
}

void ClearStack2(SqStack2 *s) {//清除栈
	while (StackEmpty2(s) != 1) {
		Pop2(s);
	}
}

void Push2(SqStack2 *s, Elemtype2 e) {//添加元素入栈
	if (s->top >= s->stacksize) {
		s->data = (Elemtype2 *)malloc((STACK_INIT_SIZE + STACKINCREMENT) * sizeof(Elemtype2));
		s->stacksize += STACKINCREMENT;
		if (s->data != NULL) {}
		else
			printf("Push error!\n");
	} else {
		s->top++;
		s->data[s->top] = e;
	}
}

Elemtype2 Pop2(SqStack2 *s) {//删除栈顶元素并返回其值，否则返回ERROR
	if (StackEmpty2(s) != 1 && s->top >= 0) {
		Elemtype2 e = s->data[s->top];
		s->top--;
		return e;
	}
	printf("Pop error!\n");
}

int StackLength2(SqStack2 *s) {//返回栈的长度
	int len = 0, temp = s->top;
	while (temp >= 0) {
		len++;
		temp--;
	}
	return len;
}

Elemtype2 GetTop2(SqStack2 *s) {//返回栈顶元素
	if (StackEmpty2(s) != 1) {
		return s->data[s->top];
	} else
		printf("GetTop error!\n");
}

int StackTraverse2(SqStack2 *s) {//从栈底向栈顶访问每个元素
	if (StackEmpty2(s) == 1) {
		printf("栈为空！\n");
		return 0;
	}
	int temp = 0;
	while (temp <= s->top) {
		printf("%c ", s->data[temp]);
		temp++;
	}
	return 1;
}

3.实现表达式求值函数包（表达式求值.c）

#include "数组堆栈.h"
double EvaluateExpression();
int isAccepted(char);
char Precede(char, char);
double Operate(double a, char theta, double b);

int main() {
	printf("请输入一个表达式：");
	double result;
	result = EvaluateExpression();
	printf("表达式的计算结果是：%0.f", result);
	return 0;
}

int flag = 0; //如果在操作数栈有连续数字的输入，则设flag=1标记，用于多位数的计算
double EvaluateExpression() {
	SqStack1 OPTR;
	SqStack2 OPND;
	char e, theta;
	double a, b;
	e = getchar();
	OPTR = InitStack1(); //运算符栈
	Push1(&OPTR, '#');
	OPND = InitStack2(); //操作数或运算结果栈
	while (GetTop1(&OPTR) != '#' || e != '#') {
		if (e == '\n')
			break;
		if (isAccepted(e) == 1) { //如果字符是数字
			e = e - '0';
			if (flag == 1) { //是多位数
				double temp = Pop2(&OPND);
				temp = temp * 10 + e;
				Push2(&OPND, temp);
			} else {
				Push2(&OPND, e);
				flag = 1;
			}
			e = getchar();
		} else {
			flag = 0;
			switch (Precede(GetTop1(&OPTR), e)) {
				case '<'://栈顶元素优先级低，压入栈
					Push1(&OPTR, e);
					e = getchar();
					break;
				case '>'://新运算符优先级低，将前一个运算符弹出进行计算
					a = Pop2(&OPND);
					theta = Pop1(&OPTR);
					b = Pop2(&OPND); //abc
					//将计算结果再次压入运算结果栈
					Push2(&OPND, Operate(a, theta, b));
					//注意这里不用再重新获取e的值
					break;
				case '=':
					Pop1(&OPTR);//将剩下的一半括号弹出
					e = getchar();
					break;
			}
		}
	}
	return GetTop2(&OPND);//返回计算结果

}

int isAccepted(char e) { //如果字符是数字，返回1；字符是运算符，返回2；否则返回0
	char number[15] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
	char calculate[15] = {'+', '-', '(', ')', '*', '#', '/'};
	for (int i = 0; i <= 9; i++) {
		if (number[i] == e)
			return 1;
	}
	for (int i = 0; i <= 6; i++) {
		if (calculate[i] == e)
			return 2;
	}
	return 0;
}

char Precede(char a, char b) {
	if (b == '+' || b == '-') {
		if (a == '(' || a == '#')
			return '<';
		else
			return '>';
	} else if (b == '*' || b == '/') {
		if (a == '*' || a == '/' || a == ')')
			return '>';
		else
			return '<';
	} else if (b == '(')
		return '<';
	else if (b == ')') {
		if (a != '(')
			return '>';
		else
			return '=';
	} else if (b == '#') {
		if (a != '#')
			return '>';
		else
			return '=';
	}

}

double Operate(double a, char theta, double b) {
	if (b == 0) {
		printf("Conflicts with calculation rules!\n");
		return;
	}
	if (theta == '+')
		return a + b;
	else if (theta == '-')
		return b - a;//因为栈先弹出减数，所以要交换顺序
	else if (theta == '*')
		return a * b;
	else if (theta == '/')
		return b / a;//因为栈先弹出除数，所以要交换顺序
}

4.测试输出：

有错误欢迎指正喔！！\\(^-^)//