[数据结构与算法]C语言数据结构 3.1 ：表达式求值

摘要：

表达式求值是栈的一个很重要的应用，由于我没有学过c++,看不懂老师的帖子里的那一份代码，所以自己用c语言实现了一遍，主要运用的思想是将中缀表达式转化为逆波兰表达式，然后再利用栈求逆波兰表达式的值。

算法思路：

1.将中缀表达式转化为逆波兰表达式：

由于逆波兰表达式的转换是一种很经典的算法，百度上的解释比我自己解释的会更好，所以直接引用百度上的算法说明：

1、首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。

2、读入一个用中缀表示的简单算术表达式。

3、从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则分析到该数字串的结束并将该数字串直接输出到后缀表达式中。

4、如果不是数字，该字符则是运算符，此时需比较优先关系。

具体做法是：将该字符与运算符栈顶的运算符的优先关系相比较。如果该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。若不是的话，则将栈顶的运算符从栈中弹出，直到栈顶运算符的优先级低于当前运算符，将该字符入栈。

5、重复步骤1～2，直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。

另外在我的算法中我首先是把字符串转化为了一个二维数组，即每一行代表了一个数字或者一个符号。

/**
 * @brief 用于将中缀表达式转化为逆波兰表达式
 *
 * @param rpn 用于保存逆波兰表达式的二维数组
 * @param str 需要计算的表达式
 * @param strlength 表达式的长度
 *
 * @return 逆波兰表达式的长度
 */
int getRPN(char **rpn, char *str, int strlength) {

	//将字符串转化为中缀表达式（带有括号）
	char **suffixExpression;
	suffixExpression = (char**)calloc(30, sizeof(char*));
	for (int i = 0; i < 30; ++i) {
		suffixExpression[i] = (char*)calloc(5, sizeof(char));
	}

	int suffixLength = 0;
	int flag = 0;
	for (int i = 0; i < strlength ; i++) {
		if (str[i] >= '0' && str[i] <= '9') {
			if (i == 0 ) {
				suffixExpression[suffixLength][i] = str[i];
				suffixLength++;
				flag++;
			} else if ((str[i - 1] >= '0' && str[i - 1] <= '9') || (str[i - 1] == '-' && flag != 0)) {
				suffixLength--;
				suffixExpression[suffixLength][flag] = str[i];
				suffixLength++;
				flag++;
			} else {
				flag = 0;
				suffixExpression[suffixLength][flag] = str[i];
				suffixLength++;
				flag++;
			}
		} else if (str[i] == '-') {
			if (i == 0 || (str[i - 1] == '+' || str[i - 1] == '-' || str[i - 1] == '*' || str[i - 1] == '/' || str[i - 1] == '(')) {
				suffixExpression[suffixLength][0] = str[i];
				suffixLength++;
				flag = 1;
			} else {
				suffixExpression[suffixLength][0] = str[i];
				suffixLength++;
				flag = 0;
			}
		} else {
			suffixExpression[suffixLength][0] = str[i];
			suffixLength++;
			flag = 0;
		}
	}
	suffixLength--;
	//打印一下中缀表达式
	for (int i = 0; i < suffixLength ; i++) {
		printf("%s\n", suffixExpression[i]);
	}
	printf("\n");

	//创建一个栈用于保存符号
	CharStackPtr z = charStackInit();
	int length = 0;//后缀表达式的长度

	//转化过程
	for (int i = 0; i < suffixLength ; i++) {
		if ((suffixExpression[i][0] >= '0' && suffixExpression[i][0] <= '9') || (suffixExpression[i][0] == '-' && strlen(suffixExpression[i]) > 1)) {
			strcpy(rpn[length], suffixExpression[i]);
			length++;
		} else if (suffixExpression[i][0] == '(' || StackIsEmpty(z) || GetTop(z) == '(') { // 栈为空或栈顶为左括号 入栈
			push(z, suffixExpression[i][0]);
		} else if (suffixExpression[i][0] == ')') { // 如果为右括号
			do {
				rpn[length][0] = pop(z);
				length++;
			} while (GetTop(z) != '(' );
			pop(z); // 删除左括号
		} else if (check(GetTop(z), suffixExpression[i][0])) { // 为其它符号则判断优先级，当当前符号优先级大于栈顶符号优先级的时候，直接入栈
			push(z, suffixExpression[i][0]);
		} else { // 当前符号优先级小于或等于栈顶符号优先级的时候，先将栈顶符号出栈加入表达式中，再和之后的栈顶符号比较，直到当前符号优先级大于栈顶符号优先级
			do {
				rpn[length][0] = pop(z);
				length++;
			} while (z->top != -1 && !(check(GetTop(z), suffixExpression[i][0]) || GetTop(z) == '('));
			push(z, suffixExpression[i][0]);
		}
	}
	while (!StackIsEmpty(z)) { // 栈内有剩余运算符则加入表达式
		rpn[length][0] = pop(z);
		length++;
	}
	//打印一下逆波兰表达式
	for (int i = 0; i < length + 3; i++) {
		printf("%s\n", rpn[i]);
	}
	printf("\n");
	return length;
}

2.计算逆波兰表达式：

此算法的原理很简单，遇到数字时将数字压入栈内，遇到运算符时，把栈的最上面的两个数字拿出来做对应的运算，再压回栈中，最后栈中只有一个数据，即为计算的最终结果。

代码：

/**
 * @brief 计算逆波兰表达式
 *
 * @param tokens 逆波兰表达式的二维数组
 * @param tokensSize 大小
 *
 * @return 计算结果
 */
int evalRPN(char** tokens, int tokensSize) {
	CharStackPtr s = charStackInit();
	int sum = 0;
	for (int i = 0; i < tokensSize; i++) {
		switch (tokens[i][0]) {
			case '+':
				s->data[s->top - 1] = s->data[s->top] + s->data[s->top - 1];
				s->top--;
				break;
			case '-':
				if (strlen(tokens[i]) > 1) {
					s->top++;
					sum = 0;
					for (int j = 1; j < (int)strlen(tokens[i]); j++) {
						sum = sum * 10 + (tokens[i][j] - '0');
					}
					s->data[s->top] = -sum;
				} else {
					s->data[s->top - 1] = s->data[s->top - 1] - s->data[s->top];
					s->top--;
				}
				break;
			case'*':
				s->data[s->top - 1] = s->data[s->top] * s->data[s->top - 1];
				s->top--;
				break;
			case'/':
				s->data[s->top - 1] = s->data[s->top - 1] / s->data[s->top];
				s->top--;
				break;
			default:
				s->top++;
				sum = 0;
				for (int j = 0; j < (int)strlen(tokens[i]); j++) {
					sum = sum * 10 + (tokens[i][j] - '0');
				}
				s->data[s->top] = sum;
		}
	}
	return s->data[s->top];
}

3.完整代码：

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

#define STACK_MAX_SIZE 30

/**
 * 定义了栈的结构体，top为栈顶，data为实现站的数组
 */
typedef struct CharStack {
	int top;
	int data[STACK_MAX_SIZE];
}*CharStackPtr;

/**
 * @brief 输出这个栈的所有元素
 *
 * @param paraStack 指向站的指针
 */
void outputStack(CharStackPtr paraStack) {
	for (int i = 0; i <= paraStack->top; i++) {
		printf("%c ", paraStack->data[i]);
	}
	printf("\r\n");
}

/**
 * @brief 创建并初始化一个空栈
 *
 * @return 指向这个站的指针
 */
CharStackPtr charStackInit() {
	CharStackPtr resultPtr = (CharStackPtr)malloc(sizeof(CharStack));
	resultPtr->top = -1;

	return resultPtr;
}

/**
 * @brief 入栈操作
 *
 * @param paraStackPtr 指向栈的指针
 * @param paraValue 放入栈的操作
 */
void push(CharStackPtr paraStackPtr, int paraValue) {
	//检查是否还有剩余空间
	if (paraStackPtr->top >= STACK_MAX_SIZE - 1) {
		printf("Cannot push element: stack full.\r\n");
		return;
	}

	//更新top的值
	paraStackPtr->top++;

	//放入元素
	paraStackPtr->data[paraStackPtr->top] = paraValue;
}

/**
 * @brief 出栈操作
 *
 * @param paraStackPtr 指向栈的指针
 *
 * @return 出栈的数据
 */
char pop(CharStackPtr paraStackPtr) {
	// 检查栈是否为空
	if (paraStackPtr->top < 0) {
		printf("Cannot pop element: stack empty.\r\n");
		return '\0';
	}

	// 更新top
	paraStackPtr->top --;

	// 返回出栈的数据
	return paraStackPtr->data[paraStackPtr->top + 1];
}

/**
 * @brief 检查栈是否为空
 *
 * @param s
 *
 * @return
 */
bool StackIsEmpty(CharStackPtr s) {
	return (s->top == -1 ? true : false);
}

/**
 * @brief 得到栈顶元素
 *
 * @param s
 *
 * @return
 */
char GetTop(CharStackPtr s) {
	return s->data[s->top];
}

/**
 * @brief 比较优先级
 *
 * @param ch1
 * @param ch2
 *
 * @return
 */
bool check(char ch1, char ch2) { // 只有ch1的优先级小于ch2的优先级时返回true
	if ((ch1 == '+' || ch1 == '-') && (ch2 == '*' || ch2 == '/')) {
		return true;
	}
	return false;
}

/**
 * @brief 计算逆波兰表达式
 *
 * @param tokens 逆波兰表达式的二维数组
 * @param tokensSize 大小
 *
 * @return 计算结果
 */
int evalRPN(char** tokens, int tokensSize) {
	CharStackPtr s = charStackInit();
	int sum = 0;
	for (int i = 0; i < tokensSize; i++) {
		switch (tokens[i][0]) {
			case '+':
				s->data[s->top - 1] = s->data[s->top] + s->data[s->top - 1];
				s->top--;
				break;
			case '-':
				if (strlen(tokens[i]) > 1) {
					s->top++;
					sum = 0;
					for (int j = 1; j < (int)strlen(tokens[i]); j++) {
						sum = sum * 10 + (tokens[i][j] - '0');
					}
					s->data[s->top] = -sum;
				} else {
					s->data[s->top - 1] = s->data[s->top - 1] - s->data[s->top];
					s->top--;
				}
				break;
			case'*':
				s->data[s->top - 1] = s->data[s->top] * s->data[s->top - 1];
				s->top--;
				break;
			case'/':
				s->data[s->top - 1] = s->data[s->top - 1] / s->data[s->top];
				s->top--;
				break;
			default:
				s->top++;
				sum = 0;
				for (int j = 0; j < (int)strlen(tokens[i]); j++) {
					sum = sum * 10 + (tokens[i][j] - '0');
				}
				s->data[s->top] = sum;
		}
	}
	return s->data[s->top];
}

int getRPN(char **rpn, char *str, int strlength) {

	//将字符串转化为中缀表达式（带有括号）
	char **suffixExpression;
	suffixExpression = (char**)calloc(30, sizeof(char*));
	for (int i = 0; i < 30; ++i) {
		suffixExpression[i] = (char*)calloc(5, sizeof(char));
	}

	int suffixLength = 0;
	int flag = 0;
	for (int i = 0; i < strlength ; i++) {
		if (str[i] >= '0' && str[i] <= '9') {
			if (i == 0 ) {
				suffixExpression[suffixLength][i] = str[i];
				suffixLength++;
				flag++;
			} else if ((str[i - 1] >= '0' && str[i - 1] <= '9') || (str[i - 1] == '-' && flag != 0)) {
				suffixLength--;
				suffixExpression[suffixLength][flag] = str[i];
				suffixLength++;
				flag++;
			} else {
				flag = 0;
				suffixExpression[suffixLength][flag] = str[i];
				suffixLength++;
				flag++;
			}
		} else if (str[i] == '-') {
			if (i == 0 || (str[i - 1] == '+' || str[i - 1] == '-' || str[i - 1] == '*' || str[i - 1] == '/' || str[i - 1] == '(')) {
				suffixExpression[suffixLength][0] = str[i];
				suffixLength++;
				flag = 1;
			} else {
				suffixExpression[suffixLength][0] = str[i];
				suffixLength++;
				flag = 0;
			}
		} else {
			suffixExpression[suffixLength][0] = str[i];
			suffixLength++;
			flag = 0;
		}
	}
	suffixLength--;
	//打印一下中缀表达式
	for (int i = 0; i < suffixLength ; i++) {
		printf("%s\n", suffixExpression[i]);
	}
	printf("\n");

	//创建一个栈用于保存符号
	CharStackPtr z = charStackInit();
	int length = 0;//后缀表达式的长度

	//转化过程
	for (int i = 0; i < suffixLength ; i++) {
		if ((suffixExpression[i][0] >= '0' && suffixExpression[i][0] <= '9') || (suffixExpression[i][0] == '-' && strlen(suffixExpression[i]) > 1)) {
			strcpy(rpn[length], suffixExpression[i]);
			length++;
		} else if (suffixExpression[i][0] == '(' || StackIsEmpty(z) || GetTop(z) == '(') { // 栈为空或栈顶为左括号 入栈
			push(z, suffixExpression[i][0]);
		} else if (suffixExpression[i][0] == ')') { // 如果为右括号
			do {
				rpn[length][0] = pop(z);
				length++;
			} while (GetTop(z) != '(' );
			pop(z); // 删除左括号
		} else if (check(GetTop(z), suffixExpression[i][0])) { // 为其它符号则判断优先级，当当前符号优先级大于栈顶符号优先级的时候，直接入栈
			push(z, suffixExpression[i][0]);
		} else { // 当前符号优先级小于或等于栈顶符号优先级的时候，先将栈顶符号出栈加入表达式中，再和之后的栈顶符号比较，直到当前符号优先级大于栈顶符号优先级
			do {
				rpn[length][0] = pop(z);
				length++;
			} while (z->top != -1 && !(check(GetTop(z), suffixExpression[i][0]) || GetTop(z) == '('));
			push(z, suffixExpression[i][0]);
		}
	}
	while (!StackIsEmpty(z)) { // 栈内有剩余运算符则加入表达式
		rpn[length][0] = pop(z);
		length++;
	}
	//打印一下逆波兰表达式
	for (int i = 0; i < length + 3; i++) {
		printf("%s\n", rpn[i]);
	}
	printf("\n");
	return length;
}

int main() {
	char str[] = "3*4+5";
	char **rpn;
	rpn = (char**)calloc(30, sizeof(char*));
	for (int i = 0; i < 30; ++i) {
		rpn[i] = (char*)calloc(5, sizeof(char));
	}
	int length;
	length = getRPN(rpn, str, sizeof(str));
	printf("%d", evalRPN(rpn, length));
}

?总结：

代码中实现了括号嵌套的情况，可以计算负数，但是不能计算一些复杂的运算比如平方，同时因为时间原因没有实现double类型的数字的运算，但是思路很简单，在把表达式字符串转化为二维数组的时候设置可以判断符号' . '，在运算逆波兰表达式的时候直接调用将字符串转化为对应数字的函数即可；另外储存表达式的结构最好用链表来实现。

如有bug请大家指正。

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖