请帮我写一个程序,实现括号栈并判断括号是否匹配
时间: 2023-05-12 15:04:05 浏览: 61
好的,以下是实现括号栈并判断括号是否匹配的 Python 代码:
```python
def is_valid(s: str) -> bool:
stack = []
mapping = {")": "(", "}": "{", "]": "["}
for char in s:
if char in mapping:
top_element = stack.pop() if stack else '#'
if mapping[char] != top_element:
return False
else:
stack.append(char)
return not stack
print(is_valid("()[]{}")) # True
print(is_valid("([)]")) # False
```
这个程序使用栈来判断括号是否匹配。我们遍历字符串中的每个字符,如果是左括号,就将其压入栈中;如果是右括号,就将栈顶元素弹出并与当前字符进行匹配。如果匹配成功,就继续遍历;否则,就返回 False。最后,如果栈为空,就说明所有括号都匹配成功,返回 True;否则,返回 False。
希望这个程序能够帮到你!
相关问题
请用c++实现一个括号栈并判断括号是否匹配
好的,以下是用 C 实现一个括号栈并判断括号是否匹配的代码:
```
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_SIZE 100
typedef struct {
char data[MAX_SIZE];
int top;
} Stack;
void init(Stack *s) {
s->top = -1;
}
bool is_empty(Stack *s) {
return s->top == -1;
}
bool is_full(Stack *s) {
return s->top == MAX_SIZE - 1;
}
void push(Stack *s, char c) {
if (is_full(s)) {
printf("Stack overflow!\n");
exit(EXIT_FAILURE);
}
s->data[++s->top] = c;
}
char pop(Stack *s) {
if (is_empty(s)) {
printf("Stack underflow!\n");
exit(EXIT_FAILURE);
}
return s->data[s->top--];
}
bool is_match(char left, char right) {
return (left == '(' && right == ')') || (left == '[' && right == ']') || (left == '{' && right == '}');
}
bool is_balanced(char *expr) {
Stack s;
init(&s);
for (int i = 0; expr[i] != '\0'; i++) {
if (expr[i] == '(' || expr[i] == '[' || expr[i] == '{') {
push(&s, expr[i]);
} else if (expr[i] == ')' || expr[i] == ']' || expr[i] == '}') {
if (is_empty(&s) || !is_match(pop(&s), expr[i])) {
return false;
}
}
}
return is_empty(&s);
}
int main() {
char expr[MAX_SIZE];
printf("Enter an expression: ");
scanf("%s", expr);
if (is_balanced(expr)) {
printf("The expression is balanced.\n");
} else {
printf("The expression is not balanced.\n");
}
return 0;
}
```
如果输入的表达式是平衡的,程序会输出"The expression is balanced.",否则会输出"The expression is not balanced."。
希望这个回答能够帮到你!
c语言用栈写一个括号匹配
以下是一个使用栈来判断括号匹配的C语言程序:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define STACK_SIZE 100
//定义栈结构体
typedef struct {
char data[STACK_SIZE];
int top;
} Stack;
//初始化栈
void initStack(Stack *s) {
s->top = -1;
}
//判断栈是否为空
int isEmpty(Stack *s) {
return s->top == -1;
}
//判断栈是否已满
int isFull(Stack *s) {
return s->top == STACK_SIZE - 1;
}
//入栈
void push(Stack *s, char c) {
if (isFull(s)) {
printf("Stack is full.\n");
exit(1);
}
s->data[++s->top] = c;
}
//出栈
char pop(Stack *s) {
if (isEmpty(s)) {
printf("Stack is empty.\n");
exit(1);
}
return s->data[s->top--];
}
//获取栈顶元素
char peek(Stack *s) {
if (isEmpty(s)) {
printf("Stack is empty.\n");
exit(1);
}
return s->data[s->top];
}
//判断括号是否匹配
int isMatch(char left, char right) {
if (left == '(' && right == ')')
return 1;
else if (left == '[' && right == ']')
return 1;
else if (left == '{' && right == '}')
return 1;
else
return 0;
}
//判断整个字符串中的括号是否匹配
int isBalanced(char *s) {
Stack stack;
initStack(&stack);
int len = strlen(s);
for (int i = 0; i < len; i++) {
char c = s[i];
if (c == '(' || c == '[' || c == '{') {
push(&stack, c);
} else if (c == ')' || c == ']' || c == '}') {
if (isEmpty(&stack))
return 0;
char left = pop(&stack);
if (!isMatch(left, c))
return 0;
}
}
return isEmpty(&stack);
}
int main() {
char s[100];
printf("Enter a string: ");
scanf("%s", s);
if (isBalanced(s)) {
printf("The string is balanced.\n");
} else {
printf("The string is not balanced.\n");
}
return 0;
}
```
程序先定义了一个栈结构体,并实现了相关的栈操作函数。其中,isMatch函数用于判断左右括号是否匹配,isBalanced函数用于判断整个字符串中的括号是否匹配。
在main函数中,程序首先读入一个字符串,然后调用isBalanced函数判断该字符串中的括号是否匹配,并输出相应的结果。