（CC++）数据结构与算法U+平台第三章作业

作业详解

• 题目：关于中序表达式与后续表达式
• • 答案：C
  • 详解：
  • • 1.what中缀what后缀？
    • 2.中缀转化为后缀的方法
    • 3.转换上实例
    • 4.上代码
    • 5.此题解

---

题目：关于中序表达式与后续表达式

答案：C 详解： 1.what中缀what后缀？

就以这道题为例或者如(1+2)*(4-5)，其实这种常见的表达式是我们一直所用的，是中序表达式。

但是,计算机中不能直接用中缀表达式计算,形如(1+2)*(4-5)之类的，计算机时看不懂的，但是计算机可以很容易的通过后缀表达式来计算我们所输入的算式。

所以我们就需要把中缀表达式转换为后缀表达式。

后缀式即逆波兰式，是波兰逻辑学家卢卡西维奇（Lukasiewicz)发明的一种表示表达式的方法。

这种表示方式把运算符写在运算对象的后面，例如，把a+b写成ab+，所以也称为后缀式。

这种表示法的优点是根据运算对象和算符的出现次序进行计算，不需要使用括号，也便于用械实现求值。

对于表达式x:=(a+b)(c+d)，其后缀式为xab+cd+:=， 则对于(1+2)x(4-5)，他的后缀表达式时12+45-x，括号时不要的。

简单来说，就是计算机没法和人类一样直观思考，只能一步步的通过指令进行运行，所以我们要把输入的中缀表达式转化为后缀表达式。

2.中缀转化为后缀的方法

1.遇到 *** 作数：直接输出（添加到后缀表达式中）、
2.栈为空时，遇到运算符，直接入栈
3.遇到左括号时：将其入栈
4.遇到要右括号时：执行出栈 *** 作，括号是不进入后缀表达式的，直到d出栈的是左括号
5.遇到运算符：（加减乘除）d出栈里所有优先级大于或等于该元素的栈顶元素，注意左括号，然后将该运算符入栈
6.当遍历完中序表达式时，d出所有的栈里元素

3.转换上实例

就以此题目为例a-(b-c/d)*e
遇到a：直接输出
后缀表达式：a
堆栈：空
遇到-：堆栈：空，所以入栈
后缀表达式：a
堆栈：-
遇到(：入栈
后缀表达式：a
堆栈：-(
遇到b：输出
后缀表达式：ab
堆栈：-(
遇到-：堆栈不为空，且没有优先级大于-，入栈
后缀表达式：ab
堆栈：-(-
遇到c:输出
后缀表达式：abc
堆栈：-(-
遇到/：堆栈不为空，且没有优先级大于/，入栈
后缀表达式：abc
堆栈：-(-/
遇到d：输出
后缀表达式：abcd
堆栈：-(-/
遇到)：右括号，则执行出栈 *** 作，括号是不进入后缀表达式的，直到d出栈的是左括号
后缀表达式：abcd/-
堆栈：-
遇到x：堆栈不为空，且没有优先级大于x，入栈
后缀表达式：abcd/-
堆栈：-x
遇到e：输出
后缀表达式：abcd/-e
堆栈：-x
遍历完成：d栈
后缀表达式：abcd/-ex-
堆栈：空
结束程序，转换完成。

4.上代码

主函数代码

int main() {
	char cal[50];
	char c, e;
	SqStack s;
	initStack(&s);
	printf("请输入中缀表达式 输入#表示结束\n");
	scanf_s("%c", &c);
	while (c != '#')
	{
		while (c>='0' && c<='9')
		{
			printf("%c ", c);
			scanf_s("%c", &c);
			if (c<'0' || c>'9')
			{
				printf(" ");
			}
		}
		if (c == ')')
		{
			Pop(&s, &e);
			while (e != '(')
			{
				printf("%c ", e);
				Pop(&s, &e);
			}
		}
		else if (c == '+' || c == '-')
		{
			if (!StackLen(s))
			{
				Push(&s, c);
			}
			else {
				do
				{
					Pop(&s, &e);
					if (e == '(')
					{
						Push(&s, e);
					}
					else {
						printf("%c ", e);
					}
				} while (StackLen(s) && e!='(');
				Push(&s, c);
			}
		}else if (c=='*' || c=='/' || c=='(')
		{
			Push(&s, c);
		}else if (c=='#')
		{
			break;
		}
		else {
			printf("出错，输入格式错误");
			return -1;
		}
		scanf_s("%c", &c);
	}
	while (StackLen(s))
	{
		Pop(&s, &e);
		printf("%c ", e);
	}
	return 0;cd
}

5.此题解

最难的转换理解后，我们直接看第三条，寻找堆栈最大时的大小

可知大小为4