数据结构——第三章 栈与队列（2）

1.括号匹配

void matching(char str[])
{//创建空栈LinkStack S;S = NULL;int k;int flag = 1;char e;for (k = 0; str[k] != '\0'; k++){if (str[k] != '(' && str[k] != ')' && str[k] != '[' && str[k] != ']' && str[k] != '{' && str[k] != '}'){//非括号处理continue;}switch (str[k])//对括号进行匹配处理{case '(':case '{':case '['://遇到左括号进栈PushLinkStack(&S, str[k]);break;case ')'://遇到右圆括号if (S != NULL){GetTopStack(S, &e);if (e == '('){PopLinkStack(&S, &e);//栈顶是左圆括号，匹配成功}else{flag = 0;//栈顶不是左圆括号，匹配失败}}else{flag = 0;//栈空，匹配失败}break;case ']'://遇到右方括号if (S != NULL){GetTopStack(S, &e);if (e == '['){PopLinkStack(&S, &e);//栈顶是左方括号，匹配成功}else{flag = 0;//栈顶不是左方括号，匹配失败}}else{flag = 0;//栈空，匹配失败}break;case '}'://遇右花括号if (S != NULL){GetTopStack(S, &e);if (e == '}'){PopLinkStack(&S, &e);//栈顶是左右花括号，匹配成功}else{flag = 0;//栈顶不是左右花括号，匹配失败}}else{flag = 0;//栈空，匹配失败}break;                      }//switch}//forif (flag == 1 && S == NULL){printf("括号匹配!\n");}else{printf("括号不匹配！\n");}
}

2.表达式求值

C语言有着丰富的表示式，那么C的编译器是如何处理表达式的呢？

2.1.算术表示式的形式

数学上的算法表达式通常包括操作数和运算符。

• 操作数：简单变量或表达式，用s1,s2表示。
• 运算符：+、-，*，/，（，），用op表示。

通常的算术表达形式即为数学表达式形式，如3*(5-2)+7。由于运算符的优先级，因此求值不一定能够按照从左向右的顺序执行。如果能将算术表示式转成易于从左向右的顺序执行，即可大大提高计算机的执行效率。
算术表达式除了数学上的表达形式外，还有如下三种表达形式。
（1）中缀表达式（运算符位于两个操作数之间）：s1 op s2
（2）前缀表达式（运算符位于两个操作数之前）: op s1 s2
（3）后缀表达式（运算符位于两个操作数之后）: s1 s2 op

以算术表达式 3*(5-2)+7为例，下面给出算术表达形式的步骤。依次处理算术表达式中级别较低的运算符，为了从形式上明确运算符的两个操作对象，约定当操作对象是表达式时，用一对花括号括起来，结果如下。

• 中缀表达式的处理顺序。
  ①处理‘+’：{3 * (5-2)} + 7; ②处理‘ * ’：3 * {5-2} +7; ③处理‘-’：3 * 5-2+7
• 前缀表达式的处理顺序。
  ①处理‘+’：+{3 * （5-2）}7；②处理‘ * ’：+ * 3{（5-2）}7；③处理‘-’：+ * 3-527
• 后缀表达式的处理顺序。
  ①处理‘+’：{3 * （5-2）}7+；②处理‘ * ’：3{（5-2）} * 7+；③处理‘-’：352 - * 7+

不难看出：三种表达式的操作数顺序相同，但运算符顺序不一。其中，中缀表达式丢失了算术表达式中的括号信息，致使运算符的运算顺序不能确定，计算会出现二义性；前缀表达式的运算规则是连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小的表达式，由于运算符的顺序与计算机算顺序不一致，因此需要多次扫描前缀式，才能得到表达式的计算，效率低；后缀表达式中的运算规则是连续出现两个操作数和在它们之后紧靠它们的运算符构成一个最小的表达式，由于运算符的顺序与计算机顺序一致，因此只需一次扫描后缀式，即可完成表达式的计算，效率高。

2.2.后缀表达式求值

求值过程：后缀表达式是一个字符串，为了方便处理，以‘#’结束。用一个栈（假定数据元素类型为整型）来存放操作数和中间计算结果。对后缀表达式从左向右依次扫描，若是操作数，则将字符转换成整数进栈；若是运算符，则连续出栈两次，第一出栈的元素是第二个操作数，第二次出栈的元素是第一个操作数，根据当前的运算符做相应的运算，并将结果进栈，直到‘#’为止。此时栈中只剩下一个元素，即最后的结果，出栈即刻。

int suffix_value(char a[])//a指向后缀表达式
{int i = 0, x1,x2, result;LinkStack S=NULL;while (a[i]!='#'){switch (a[i]){case '+':PopLinkStack(&S, &x2);PopLinkStack(&S, &x1);PushLinkStack(&S, x1 + x2);break;case '-':PopLinkStack(&S, &x2);PopLinkStack(&S, &x1);PushLinkStack(&S, x1 - x2);break;case '*':PopLinkStack(&S, &x2);PopLinkStack(&S, &x1);PushLinkStack(&S, x1 * x2);break;case '/':PopLinkStack(&S, &x2);PopLinkStack(&S, &x1);PushLinkStack(&S, x1 / x2);break;default:PushLinkStack(&S, a[i] - '0');}//end_switchi++;//访问下一个}PopLinkStack(&S, &result);return result;
}//suffix_value

2.3.将算术表达式转换为后缀表达式

为了方便将算术表达式转换成后缀表达式，不妨在算术表达式的末尾增加一个字符‘#’，在算术运算符中增加一个‘#’运算符。
用一个字符栈来存放运算符。先用‘#’初始化字符栈，再对表达式字符串中的每一个字符从左到右依次做一下处理。
（1）如果当前字符是操作数，则将其存放到后缀表达式中数组中。
（2）如果当前字符是运算符，则考虑它是否进栈。
设当前运算符为op，则
（1）当op == ‘(’ 时，op直接进栈。
（2）当op == ‘)’ 时，栈顶运算符依次出栈，并依次将其按顺序存放到后缀表达式数组，直到遇到’)‘为止。注意：’('只是出栈，不存放到后缀表达式数组。
（3）当op的优先级高于栈顶运算符的优先级时，op进栈；否则，栈顶的运算符依次出栈，存放到后缀表达式数组中，直到栈顶的运算符的优先级低于op，op进栈。
（4）当op == ‘#’ ,栈顶运算符依次出栈，存放到后缀表达式数组，直到栈顶运算符为‘#’，算法结束。
设运算符的优先级为#，（，+或-，*或/，从左到右由低到高。
判断优先级的算法

int prior(char a)
{if (a == '*' || a == '/'){return 4;}else if (a == '-' || a == '+'){return 3;}else if (a == '('){return 2;}else if(a=='#'){return 1;}return 0;
}

将算术表达式转换成后缀表达式的算法如下：
【算法】

void Transformation(char a[], char suff[])
{//a指向算术表达式，以'#'结束，栈用于存放运算符//将a指向的算术表达式转换成由suff指向的后缀表达式int i = 0;int k = 0;int n;char ch;LinkStack s;s = NULL;PushLinkStack(&s, '#');n = strlen(a);//在表达式的末尾添加一个#a[n] ='#';a[n + 1] = '\0';while (a[i] != '\0'){if (a[i] >= '0' && a[i] <= '9'){//是操作数，直接存入后缀表达式suff[k++] = a[i];}//是运算符else{switch (a[i]){case '(':PushLinkStack(&s, a[i]);//进栈break;case ')'://将左圆括号之上的运算符依次出栈并发送到后缀表达式，左圆括号只是出栈PopLinkStack(&s, &ch);while (ch != '('){suff[k++] = ch;PopLinkStack(&s, &ch);}break;/*比较表达式当前的运算符a[i]和栈顶运算符的ch的优先级，如果a[i]高于ch，a[i]进栈；反之，栈内高于a[i]的运算符依次出栈并发往后缀表达式直到栈顶运算符优先级低，在将a[i]进栈*/default:GetTopStack(s, &ch);while (prior(ch) >= prior(a[i])){suff[k++] = ch;GetTopStack(s, &ch);}if (a[i] != '#'){PushLinkStack(&s, a[i]);}}//end_switch}//end_elsei++;}//end_whilesuff[k] = '\0';//保证suff存放的是字符串
}//Transformation

以上算法仅适用用于操作数是个位数。要计算任意实数，需要解决如下问题。
（1）后缀表达式中的操作数与操作数之间如何隔开。
（2）操作数栈的类型是什么？
（3）如何将一个数字串转换为一个实数？
（4）操作数为负数的时，如何处理？
例如，算术表达式为-3+（-15.7+9）* 4.25 + 7/8.2
（1）先处理负数的情况。
原则：第一个字符为‘-’时，前面加0；‘("之后是’-‘，在’('之后加0。
（2）在操作数与操作数之间加空格。

2.4.算术表达式直接求值

算法的主要步骤如下。
（1）创建两个栈，一个是运算符栈（初始化时，将’#'进栈），另一个是操作数中间结果栈。
（2）对算术表达式从左向右的依次扫描。
①如果算数表达式的当前字符是操作数，则将算术表达式当前的字符转换成整数进操作数栈。
②如果算术表达式的当前字符是运算符，则将运算符栈的栈顶运算符进行比较。

• 如果算术表达式的当前运算符优先级低于栈顶的运算符优先级，则栈顶的运算符出栈，从操作数栈连续弹出两个操作数，先出的操作数第二运算对象，后出的操作数是第一个运算对象，对两个操作数做出栈运算符对应的操作，并将计算结果结果进操作数栈，直至栈顶运算符的优先级低于算术表达式的当前运算符的优先级为止，再将算术表达式的当前运算符进算符栈。
• 如果算术表达式的当前运算符优先级高于栈顶的运算符优先级，则将算术表达式的当前运算符进运算符栈。

（3）如果算术表达式的当前运算符是’#‘，则依次弹出运算符栈的运算符，同时从操作数连续弹出两个操作数做相应的操作，并将计算结果进操作数栈，直至栈顶的运算符为’#',算法结束。

3.栈与递归

3.1.递归算法

递归是计算机数值计算中的一个中要算法，它可以将复杂的运算转化为若干重复的简单运算，充分发挥计算机重复处理的特点。把递归算法推广为调用自身的方法称为递归算法。

递归实质是将一个不好或不能直接求解的“大问题”转化为一个或几个“小问题”来解决，这些小问题可以继续分解成更小的问题，直至小问题可以直接求解。下面分别介绍这两种常用的递归设计。

• 递归设计方法一
  通过将问题简化为自身更小的形式来得到问题解的方法称为递归算法，递归算法必须包含一个或多个基本公式。
  递归算法的应用条件如下：
  （1）可以将要解决的问题转化为另一个新问题，而解决这个新问题的方法与原问题的解决方法相同，并且被处理的对象的某些参数是有规律地递增或递减的。其中转化的过程成为一般公式。
  （2）必须有终止递归的条件（基本公式），即递归出口。
  编写递归算法必须做到以下几点。
  ①确定限制条件或问题的规模。
  ②确定基本公式。
  ③确定一般公式。
• 递归设计方法二
  对于一个输入规模为n的函数或问题，用某种方法把输入分割成k个子集，从而产生k个字问题，分别求解这个k个子问题，得出k个问题的字解。有些子问题可以直接得到解决，有些子问题的解决方法与原问题相同，再用某种方法把它们组合成原来问题的解。
  递归文章详细解析+题目介绍

3.2.栈与函数调用

（1）函数的嵌套调用
main()->fun()->gun()
问题1：每个函数调用完成后，执行流程转向何处？
问题2：执行流程转向被调函数后，继续向下执行，被调用的参数的内部变量在哪里保存？
（2）函数调用的管理
用高级语言编写的程序中，主调函数与被调函数之间的信息交换通过栈来进行。当一个函数在运行期间调用另一个函数时，在运行该别调函数之前，需先完成三件事。

• 将所有的实参和返回地址等信息传递给被调函数保护。
• 为被调函数的局部变量分配存储区。
• 将控制转移到被调函数的入口。

从被调函数返回调用函数之前，也应该完成三件事。

• 保存被调函数的计算结果。
• 释放被调函数中形参和局部变量的存储区。
• 依照被调函数保存的返回地址将控制转移到主调函数。

多个函数嵌套调用的规则是：先调用函数后返回，后调用函数先返回。系统对调函数的内存管理实行的“栈式管理”。

3.3.递归工作与递归函数

递归函数是指定义在一个函数的过程中直接或间接地调用该函数本身。

递归工作栈的记录是一个结构体类型的数据，包括：
（1）上一层函数调用的放回地址。
（2）局部变量（包括参数）值。
系统工作栈的栈顶工作记录对应的是当前正在调用的函数。每调一次函数，将函数的返回地址和局部变量（包括参数）表形成一个递归工作记录压入系统工作栈。每调用完一次函数，将系统工作栈的栈顶工作记录弹出，直至系统工作栈为空。栈空表明递归函数调用结束。

递归算法的特点如下。

• 优点：程序易于设计，程序结构简单精炼。
• 缺点：递归算法较难理解，可读性差；程序运行速度慢，占用相当多的系统资源空间。

3.4.递归到非递归的转换

递归的缺点很明显，所以能用循环就不要用递归。
（1）直接转换法。
如果递归算法是直接求值，不需要回溯，则只需要变量保存中间的结果，将递归结果改为循环结构。
（2）间接转换法
按照递归的执行规律进行转换，将递归调用语句改为进栈操作，将每次递归返回调用后的后续执行语句改为出栈操作。

//将任意一个整数按数字字符显示的递归函数如下void change(int x)
{int n;if (n = x / 10){change(n);//进栈}putchar(x % 10 + 48);//出栈
}
//转换成非递归
void change(int x)
{int n;STACK s;s = NULL;if (x == 0){putchar(x + 48);return;}while (x){//进栈push(s, x % 10);x /= 10;}while (!empty(s)){pop(s, n);//出栈putchar(n + 48);}putchar('\n');
}