数据结构笔记之表达式求值

1. 概念：运算是由运符和操作数组成的，DIY概念指的是左操作数、右操作数和运符之间的关系。
2. 中缀表达式：运符位于操作数之间，这是我们日常生活中最常用的表达式形式。
3. 后缀表达式：运符在操作数后面，这种表达式形式没有括号，易于解析。
4. 前缀表达式：运符在操作数前面，同样没有括号，但需要遵循不同的规则来解析。

转换过程：

1. 中缀转后缀：按照“左优先”的原则确定运符的运序序列，依次将各个运符和与其相邻的两个操作数压入栈，遇到运符则弹出栈顶的两个操作数进行运算，结果再入栈。注意：先弹出的元素是“右操作数”。这种方法避免了处理括号的问题，使得表达式的求值变得简单。
2. 后缀转中缀：从左往右扫描，遇到操作数就入栈，遇到运符则弹出栈顶的两个操作数进行运算，结果再入栈。注意：先弹出的元素是“右操作数”。
3. 中缀转前缀：同理，按照“右优先”的原则确定运符的运序序列，依次将各个运符和与其相邻的两个操作数压入栈，遇到运符则弹出栈顶的两个操作数进行运算，结果再入栈。注意：先弹出的元素是“左操作数”。

计算过程：

1. 对于后缀表达式，从左往右扫描，遇到操作数就入栈，遇到运符则弹出栈顶的两个操作数进行运算，结果再入栈。这样就可以得到最终的结果。
2. 对于前缀表达式，也是从左往右扫描，遇到操作数就入栈，遇到运符则弹出栈顶的两个操作数进行运算，结果再入栈。但是要注意，这里先弹出的元素是“左操作数”。

利用中缀转后缀求值（c语言）：

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

// 设置符号优先级
int compareReturn(char str1) {
	if (str1 == '+' || str1 == '-') {
		return 1;
	} else if (str1 == '*' || str1 == '/') {
		return 2;
	} else if (str1 == '(') {
		return 3;
	} else {
		// 此时为数字
		return -1;
	}
}

int evaluate(int b, int a, char c) {
	switch (c) {
		case '+':
			return a + b;
			break;
		case '-':
			return a - b;
			break;
		case '*':
			return a * b;
			break;
		case '/':
			return a / b;
			break;
	}
	return 0;
}

int main () {
	char s1[100];
	int top1 = -1;
	int s2[100];
	char top2 = -1;
	char str[100];
	printf("请输入中缀表达式\n");
	scanf("%s", str);
	int length = (int)strlen(str);
	for (int i = 0; i < length; ) {
		if (compareReturn(str[i]) == -1) {
			s2[++top2] = str[i] - '0';
			i++;
		} else if (str[i] == ')') {
			while (s1[top1] != '(') {
				int a1 = s2[top2--];
				int a2 = s2[top2--];
				s2[++top2] = evaluate(a1, a2, s1[top1--]);
			}
			top1--;
			i++;
		} else {

			if (top1 == -1 || compareReturn(s1[top1]) < compareReturn(str[i]) || s1[top1] == '(') {
				s1[++top1] = str[i++];
			} else {
				int a1 = s2[top2--];
				int a2 = s2[top2--];
				s2[++top2] = evaluate(a1, a2, s1[top1--]);
				s1[++top1] = str[i++];
			}

		}
	}

	while (top1 != -1) {
		int a1 = s2[top2--];
		int a2 = s2[top2--];
		s2[++top2] = evaluate(a1, a2, s1[top1--]);
	}
	printf("%d", s2[top2]);

	return 0;

}