C#数据结构：栈的应用：括号匹配问题

假设表达式中包含三种括号：圆括号、方括号和花括号，它们可互相嵌套，如 ( [ { } ]( [ ] ) )或( { ( [ ] [ ( ) ] ) } )等均为正确的格式，而 { [ ] } ) }或 { [ ( ) ] 或 ( [ ] }均为不正确的格式。

算法描述：

1.首先校验输入的括号字符是否空
2.创建一个空栈用来存储左括号
3.循环读取括号字符串，当读到左括号时，将其入栈，当读到右括号，则将右括号与栈顶左括号进行类型匹配，匹配成功则将左括出栈，否则就是为非法情况。
4.当所有的括号读取完成后，若左括号栈同时也为空了，表明匹配成功，不为空，表明左括号多余。

算法实现：

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class StackAppliction
{

    /// <summary>
    /// 括号匹配算法（栈的应用）
    /// </summary>
    /// <param name="str"></param>
    /// <returns></returns>
    public bool BracketMatch(string str)
    {
        Debug.Log(str);

        if (str == string.Empty||str==null)//校验字符括号是否为空
        {
            Debug.Log("字符括号为空！匹配失败！");
            return false;
        }

        LinkStack<char> stack = new LinkStack<char>(); //用来存储左括号(此处使用了之前自己定义的链栈结构)
        //Stack<char> stack = new Stack<char>();//系统提供的栈

        for (int i = 0; i < str.Length; i++)//读取括号字符串
        {
            switch (str[i])
            {
                case '(':
                case '[':
                case '{':
                    stack.Push(str[i]);//左括号进栈
                    break;
                case ')':
                case ']':
                case '}':
                    if (stack.IsEmpty())//使用系统提供的栈：stack.Count==0
                    {
                        Debug.Log("右括号   " + str[i] + "  多余！匹配失败！");
                        return false;
                    }
                    else
                    {
                        char left = stack.Peek();//访问左括号栈顶值

                        if (Match(left, str[i])) //判断左右括号类型
                        {
                            stack.Pop(); //匹配成功,出栈顶值
                        }
                        else
                        {
                            Debug.Log("左括号:  " + left + "  与右括号：   " + str[i] + "   不同类型！匹配失败！ ");
                            return false;
                        }
                    }
                    break;
                default:
                     break;
            }
        }

        if (stack.IsEmpty())//使用系统提供的栈：stack.Count==0
        {
            Debug.Log("匹配成功！");
            return true;
        }
        
        Debug.Log("左括号:  " + stack.Peek() + "   多余！匹配失败！");
        return false;

    }


    /// <summary>
    /// 判断左括号与右括号是否同类型
    /// </summary>
    /// <param name="l">左括号</param>
    /// <param name="r">右括号</param>
    /// <returns></returns>
    private bool Match(char l, char r)
    {
        if ((l == '(') && (r == ')'))
        {
            return true;
        }
        if ((l == '[') && (r == ']'))
        {
            return true;
        }
        if ((l == '{') && (r == '}'))
        {
            return true;
        }
        return false;

    }
}

算法测试：

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class _010_StackAppliction : MonoBehaviour
{

    void Start()
    {


        StackAppliction appliction = new StackAppliction();

        print(appliction.BracketMatch(null));

        print(appliction.BracketMatch(""));

        print(appliction.BracketMatch("({})"));

        print(appliction.BracketMatch("({fsd[f}af)"));

        print(appliction.BracketMatch("(af{af}"));

        print(appliction.BracketMatch("af{af}sf)af"));

        print(appliction.BracketMatch("(dfgd{q)"));

        print("判断是否平衡圆括号---------------");

        print("是否平衡圆括号:"+appliction.BracketMatch("()()"));
        print("是否平衡圆括号:" + appliction.BracketMatch("())"));
        print("是否平衡圆括号:" + appliction.BracketMatch("(((((())))))"));

    }
}

输出结果：

img.jpg