栈的应用括号匹配问题

问题描述

判断一个字符串中的所有左括号和右括号的类型和数量是否一致。
例如：
{aaa[bbb(ccc)ddd]} 括号匹配。
{aaa[bbb(ccc)ddd} 括号不匹配。

问题分析

可以利用栈，首先遍历字符串，遍历到左括号时，将括号入栈。遍历到右括号时与栈顶元素进行比较判断类型是否一样。

算法描述

Node

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LinkStack
{
    class Node<T>
    {
        T data;
        Node<T> next;
        
        /// <summary>
        /// 构造器
        /// </summary>
        public Node()
        {
            this.Data = default(T);
            this.Next = null;
        }

        /// <summary>
        /// 构造器
        /// </summary>
        /// <param name="data"></param>
        public Node(T data)
        {
            this.Data = data;
        }

        public T Data { get => data; set => data = value; }
        internal Node<T> Next { get => next; set => next = value; }
    }
}

LinkStack

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LinkStack
{
    class LinkStack<T>
    {
        Node<T> top;

        public LinkStack()
        {
            this.top = new Node<T>();
        }

        /// <summary>
        /// 入栈
        /// </summary>
        /// <param name="data"></param>
        public void Push(T data)
        {
            //新建节点 
            Node<T> tmp = new Node<T>(data);
            //挂载节点
            tmp.Next = this.top.Next;
            this.top.Next = tmp;
        }

        /// <summary>
        /// 出栈
        /// </summary>
        /// <returns></returns>
        public T Pop()
        {
            if (top.Next == null) return default(T);

            //保存栈顶节点
            Node<T> tmp = top.Next;
            //悬空栈顶节点
            top.Next = top.Next.Next;
            return tmp.Data;
        }

        /// <summary>
        /// 判空
        /// </summary>
        /// <returns></returns>
        public bool IsEmpty()
        {
            if (this.top.Next == null) return true;
            return false;
        }
    }
}

Program

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LinkStack
{
    class Program
    {
        static void Main(string[] args)
        {
            LinkStack<char> ls = new LinkStack<char>();

            string input = Console.ReadLine();

            for (int i = 0; i < input.Length; i++)
            {
                switch (input[i])
                {
                    case '[':
                        ls.Push('[');
                        break;
                    case '{':
                        ls.Push('{');
                        break;
                    case '(':
                        ls.Push('(');
                        break;
                    case ')':
                    case '}':
                    case ']':
                        if (ls.IsEmpty())
                        {
                            Console.WriteLine("右括号多余");
                            return;
                        }
                        else {
                            char c = ls.Pop();
                            if (!Match(c,input[i]))
                            {
                                Console.WriteLine(c);
                                Console.WriteLine(input[i]);
                                Console.WriteLine("左括号不匹配");
                                return;
                            }
                            break;
                        }
                }
            }
        }

        static bool Match(char a, char b)
        {
            switch (a)
            {
                case '[':
                    if (b == ']')
                        return true;
                    break;
                case '{':
                    if (b == '}')
                        return true;
                    break;
                case '(':
                    if (b == ')')
                        return true;
                    break;
                default:
                    return false;
            }
            return false;
        }
    }
}