括号匹配
假设有两种括号，一种圆的()，一种方的[]，嵌套顺序任意。
例如： ([]) ([][([])])
如果是左括号，则执行入栈操作，如果是右括号，出栈一个左括号判断是否与之匹配；直到最后全部匹配没有剩余则表示正确。
对之前栈的代码进行改造：
bool stack_check(SqStack *S, char *str) {
int len = strlen(str);
ElemType x;
for (int i = 0; i < len; i++) {
char a = str[i];
switch (a) {
case '(':
push(S, a);
break;
case '[':
push(S, a);
break;
case ')':
pop(S, &x);
if(x != '('){
printf("不匹配 \r\n");
return false;
}
break;
case ']':
pop(S, &x);
if(x != '['){
printf("不匹配 \r\n");
return false;
}
break;
}
}
if (stack_empty(S)){
printf("空\r\n");
return true;
}else{
return false;
}
}
表达式求值
表达式
算数四则运算的规则：
- 先乘除后加减
- 从左到右
- 先括号内，再括号外
例如 ：
4 + 2 * 3 - 10 / 5 = 4 + 6 - 10 / 5 = 10 - 10 / 5 = 10 - 1 = 8
表达式包括前缀表达式、中缀表达式和后缀表达式，前缀表达式即运算符号在前数字在后，也称为波兰式，即 - * + 3 4 5 6。中缀表达式就是我们日常书写的形式，而后缀表达式则是数字在前符号在后，也称为逆波兰式。
在计算机中，前缀表达式和后缀表达式更容易处理和操作。
所以进行表达式求值，要先将中缀表达式转换成前缀或后缀表达式。当然也可以参考书上的算符优先级法，这个接下来再学习。
从左到右扫描表达式中的数字和符号，遇到数字就进栈，遇到符号则将栈顶元素出栈然后用这个符号进行运算，再将运算结果进栈，直到最后获得计算结果。
来个栗子，就算这个吧：(5 * 2 + 1 * 8) /2
中缀表达式转后缀表达式：
待研究
手动转换：
((5 2)* (1 8)*) + 2 )/
int stack_eva(SqStack *S, char *str){
int len = strlen(str);
printf("len = %d\r\n",len);
ElemType x,y;
for (int i = 0; i < len; i++) {
char a = str[i];
switch (a) {
case '+':
pop(S, &x);
pop(S, &y);
push(S,x+y);
printStack(S);
break;
case '-':
pop(S, &x);
pop(S, &y);
push(S,x-y);
printStack(S);
break;
case '*':
pop(S, &x);
pop(S, &y);
push(S,x*y);
printStack(S);
break;
case '/':
pop(S, &x);
pop(S, &y);
push(S,y/x);
printStack(S);
break;
default:
push(S, a);
printStack(S);
break;
}
}
return 0;
}
递归
如果在一个函数、过程或数据结构的定义中又应用了它自身，那么这个函数、过程或数据结构就称为递归定义的，简称递归。
int F(int n){
if(n == 0) return 1; // n == 0 f(0) ==1 递归边界
else return n*F(n -1); // 递归式 （F(n) = F(n -1) * n）
}
执行 F(3) = F(2) * 3 = F(1) * 2 * 3 = F(0) * 1 * 2 * 3 = 1 * 1 * 2 * 3 = 6
求斐波那契数列的第 n 项：
int fib(int n){
if(n == 0) return 0;
if(n == 1) return 1;
else return fib(n - 1) + fib(n - 2);
}
