在四则运算表达式中，可以包含圆括号和方括号，而且还允许他们嵌套出现。试编写一个算法实现括号匹配

思路：

1. 遍历字符串中每个字符，如果是左括号，则入栈；如果是右括号，则弹出栈顶元素比较是否匹配。

2. 如果栈为空，或者栈顶元素与当前字符不匹配，则括号不匹配。

3. 如果字符串遍历完后，栈中还有元素，则说明括号不匹配。

代码实现（Python）：

def is_balanced(s):
    stack = []
    for c in s:
        if c == '(' or c == '[':
            stack.append(c)
        elif c == ')' and stack and stack[-1] == '(':
            stack.pop()
        elif c == ']' and stack and stack[-1] == '[':
            stack.pop()
        else:
            return False
    return not stack

# 测试代码
print(is_balanced('(1+2)*[3-(4/2)]')) # True
print(is_balanced('(1+2)*[3-4/2)]'))  # False

时间复杂度：$O(n)$，其中 $n$ 是字符串的长度。遍历一遍字符串，每个字符入栈出栈各一次，时间复杂度是 $O(n)$。

空间复杂度：$O(n)$，最坏情况下，所有左括号都入栈了，空间复杂度是 $O(n)$。

相关问题

在四则运算表达式中，可以包含圆括号和方括号，而且还允许他们嵌套出现。试编写一个算法实现括号匹配 用c语言实现

算法思路：

使用栈来解决括号匹配的问题。

从左到右扫描表达式中的每个字符，当遇到左括号时，将其压入栈中；当遇到右括号时，判断栈顶的左括号是否与之匹配，如果匹配，则弹出栈顶元素；否则，表达式括号不匹配。扫描完整个表达式后，如果栈为空，则表明括号匹配；否则，表明括号不匹配。

代码实现：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXSIZE 100

typedef struct Stack //栈的数据结构
{
char data[MAXSIZE];
int top;
}Stack;

void initStack(Stack *S); //初始化栈
int push(Stack *S,char a); //入栈
char pop(Stack *S); //出栈
int is_empty(Stack *S); //判断栈是否为空
int match(char a,char b); //判断括号是否匹配
int bracket_match(char exp[]); //括号匹配主函数

void initStack(Stack *S) //初始化栈
{
S->top=-1;
}

int push(Stack *S,char a) //入栈
{
if(S->top==MAXSIZE-1)
{
printf("Stack is full!\n");
return 0;
}
else
{
S->top++;
S->data[S->top]=a;
return 1;
}
}

char pop(Stack *S) //出栈
{
char temp;
if(is_empty(S))
{
printf("Stack is empty!\n");
return -1;
}
else
{
temp=S->data[S->top];
S->top--;
return temp;
}
}

int is_empty(Stack *S) //判断栈是否为空
{
if(S->top==-1)
return 1;
else
return 0;
}

int match(char a,char b) //判断括号是否匹配
{
if((a=='('&&b==')')||(a=='['&&b==']'))
return 1;
else
return 0;
}

int bracket_match(char exp[]) //括号匹配主函数
{
int i;
char temp;
Stack S;

initStack(&S); //初始化栈

for(i=0;exp[i]!='\0';i++) //扫描字符
{
if(exp[i]=='('||exp[i]=='[') //左括号入栈
push(&S,exp[i]);
else if(exp[i]==')'||exp[i]==']') //右括号
{
if(is_empty(&S)) //如果没有左括号与之匹配
return 0;
else
{
temp=pop(&S); //取出左括号
if(!match(temp,exp[i])) //判断括号是否匹配
return 0;
}
}
}

if(is_empty(&S)) //扫描完所有字符，如果栈为空，则括号匹配
return 1;
else
return 0;
}

int main()
{
char exp[MAXSIZE];

printf("Please enter the expression:");
gets(exp);

if(bracket_match(exp))
printf("Bracket match!\n");
else
printf("Bracket not match!\n");

return 0;
}

假设表达式中允许包含圆括号、方括号。设计一个算法采用顺序栈判断代码

可以采用顺序栈实现一个简单的算法来判断代码中的圆括号和方括号是否匹配。具体步骤如下：

1. 创建一个空栈，用于存储左括号；

2. 依次扫描代码中的每个符号，如果是左括号，则将其入栈；如果是右括号，则弹出栈顶元素判断是否与当前括号匹配，如果不匹配则说明代码中存在括号不匹配的错误；

3. 如果代码扫描完毕后，栈中仍然存在未匹配的左括号，则说明代码存在括号不匹配的错误。

具体的算法实现可以参考下面的伪代码：

function isBracketMatched(code):
    stack = empty stack
    for symbol in code:
        if symbol is left bracket:
            stack.push(symbol)
        else if symbol is right bracket:
            if stack is empty or stack.top is not matching left bracket for symbol:
                return false
            stack.pop()
    if stack is not empty:
        return false
    return true

需要注意的是，上述算法只能判断圆括号和方括号是否匹配，对于其他类型的括号（如花括号）需要根据具体情况进行修改。同时，算法还需要考虑括号嵌套的情况，即在一个括号内部还存在其他括号的情况。