堆栈队列应用

堆栈与队列运用

1、字符串匹配

思路：

按照要求模拟即可，主要是别忘了，在遇到运算符时，除了出在当前栈中，栈顶元素优先级较高的元素之外，还要将当前的运算符入栈

1、整体的规则，遇到字符直接输出
2、遇到左括号直接入栈
3、遇到右括号，直接出栈，直到出栈元素为左括号
4、遇到 ‘’ ‘/’ 将栈顶中符号为’’ ‘/‘出栈，直到为空，或者遇到括号，然后将当前操作符入栈
5、遇到’+’,’-‘将栈顶中符号为 ‘+’,’-’，’*’ ‘/’ 全部出栈 ，然后将当前操作符入栈
6、最后栈不为空，输出所有元素

代码：

char *InToPost(char *s){
	int n = strlen(s),top=-1,i=0,j=0;
	char stack[maxsize];
	char *ans = (char *)malloc(sizeof(char)*n);
	while(s[i]!='\0'){
		if((s[i]>'a' && s[i] < 'z') || (s[i]>'A' && s[i] < 'Z')){		//1、如果是字符 ，直接输出 
			ans[j++] = s[i];
			i++;
		}
		else if(s[i]=='('){												//2、如果是左括号，直接入栈 
			stack[++top] = s[i++];	
		}
		else if(s[i]==')'){												//3、如果是右括号，出栈 
			while(stack[top]!='('){
				ans[j++] = stack[top--];
			}
			top--;					//将'('出栈 
			i++;
		}
		else if(s[i] == '*' || s[i]=='/'){								//4、如果是乘法，或者除法 
			while(top!=-1 &&( stack[top]=='*' || stack[top] == '/')){
				ans[j++] = stack[top--];
			}
			stack[++top] = s[i++]; 		//将当前操作符，入栈 
		}
		else{															//5、如果是减法、加法 
			while(top!=-1 && stack[top]!='('){
				ans[j++] = stack[top--];
			}
			stack[++top] = s[i++];		//将当前操作符，入栈 
		} 
	}
	while(top!=-1){														//6、输出栈中剩余元素 
		ans[j++] = stack[top--];
	} 
	return ans; 
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

2、括号匹配

思路：

• 两个函数，一个用来遍历，一个用来返回对应的左括号函数
  • 左括号函数，如果当前的字符串为右括号，则返回对应的左括号，否则返回0
  • 遍历函数
    • 每次遍历将s[i]放入左括号函数中
      • 如果是左括号，入栈
      • 如果是右括号，和栈顶元素进行比较
        • 如果栈已经空，或者匹配失败，匹配失败
        • 匹配成功的话，出栈
    • 遍历完，如果栈为空，说明匹配成功

代码：

char Judge(char ch){				//返回对应的括号 
    if(ch == '}')  return '{';
    if(ch == ']')  return '[';
    if(ch == ')')  return '(';
    return 0;
}

bool IsValid(char * s){
    int len = strlen(s),top = 0;
    char stack[len+1],ch;
    if(len%2==1) return false;	//长度不符 
    for(int i = 0;i<len;i++){
        ch = judge(s[i]);
        if(ch){					//当前返回的是左括号 
            if( top==0 || stack[top-1] != ch)		//匹配失败 
                return false;
            top--;				//匹配成功，出栈 
        }
        else{					//如果是左括号，入栈 
            str[top++] = s[i];
        }
    }
    return top==0;				//栈空才匹配成功 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

3、进制转换

十进制转为r进制

其实进制转换用不用栈都可以，只是栈比较形象些

思路：

• 每次将十进制数对r取余得到的数入栈
• 十进制数除以r，再进行比较，直到为0
• 此时栈中元素为对应r进制的逆序数，只要出栈便可得到对应的r进制数

代码：

// 10进制转为r进制 
int *BaseChange(int n, int r){
	int stack[maxsize], top = -1,num;
	while(n!=0){			
		num = n%r;			
		stack[++top] = num;
		n = n/r;
	}				//此时，栈中保存对应r进制数的逆序，不断出栈便可得到对应的r进制数 
    while(top!=-1){
        printf("%d",stack[top--]);
    }
} 
1
2
3
4
5
6
7
8
9
10
11
12