括号匹配算法
题目来自网络搜集和常考算法，如有侵权请联系我
题目描述
给出一个仅包含字符'(',')','{','}','['和']',的字符串，判断给出的字符串是否是合法的括号序列
括号必须以正确的顺序关闭，"()"和"()[]{}"都是合法的括号序列，但"(]"和"([)]"不合法。
示例1
输入
"["
输出
false
示例2
输入
"[]"
输出
true
C++
#include
class Solution {
public:
/**
*
* @param s string字符串
* @return bool布尔型
*/
bool isValid(string s) {
// write code here
unordered_map m = { {')','('},{']','['},{'}','{'} };
stack st;
int len=s.length();
for (int i=0;i
if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
st.push(s[i]);
}
else if (st.empty()) return false;
else if (st.top() != m[s[i]]) return false;
else st.pop();
}
return st.empty();
}
};
C语言
#include
#include
int top=-1;//top变量时刻表示栈顶元素所在位置
void push(char * a,int elem){
a[++top]=elem;
}
void pop(char* a){
if (top==-1) {
return ;
}
top--;
}
char visit(char * a){
//调取栈顶元素，不等于弹栈，如果栈为空，为使程序不发生错误，返回空字符
if (top!=-1) {
return a[top];
}else{
return ' ';
}
}
int main() {
char a[30];
char bracket[100];
printf("请输入括号序列：");
scanf("%s",bracket);
getchar();
int length=(int)strlen(bracket);
for (int i=0; i
//如果是左括号，直接压栈
if (bracket[i]=='('||bracket[i]=='{') {
push(a, bracket[i]);
}else{
//如果是右边括号，判断与栈顶元素是否匹配，如果匹配，栈顶元素弹栈，程序继续运行；否则，发现括号不匹配，输出结果直接退出
if (bracket[i]==')') {
if (visit(a)=='(') {
pop(a);
}else{
printf("括号不匹配");
return 0;
}
}else{
if (visit(a)=='{') {
pop(a);
}else{
printf("括号不匹配");
return 0;
}
}
}
}
//如果所有括号匹配完成，栈内为空，说明所有括号全部匹配成功
if (top!=-1) {
printf("括号不匹配");
}else{
printf("括号匹配");
}
}
Java
import java.util.Stack;
public class Solution {
public boolean isValid(String s) {
Stack stack = new Stack();
for (char c : s.toCharArray()) {
if (c == '(')
stack.push(')');
else if (c == '{')
stack.push('}');
else if (c == '[')
stack.push(']');
else if (stack.isEmpty() || stack.pop() != c)
return false;
}
return stack.isEmpty();
}
}