[请教] 如何按照括号的顺序提取字符串中的子字符串

Question

比如说有一个字符串：
      "bus(van(suv)pickup)car(truck)"
提取顺序：
1. suv
2. van(suv)pickup
3. truck
4. bus(van(suv)pickup)car(truck)不知如何提取，请说明基本思路并附加代码（C#），非常感谢！
P.S.堆栈、链表等数据结构的实现代码可以不写。

Answer 1

结果和你要的稍微有点出入
truck
suv
van(suv)pickup
如果你想要没有出入的，需要个Pair价格Depth值，输出前对pairs进行排序
class Pair
        {
            public Pair(int begin, int end)
            {
                this.begin = begin;
                this.end = end;
            }
            public int begin;
            public int end;
        }        private void button2_Click(object sender, EventArgs e)
        {
            string source = "bus(van(suv)pickup)car(truck)";
            List<Pair> pairs = new List<Pair>();
            for (int i = 0; i<source.Length; ++i)
            {
                if (source[i] == '(')
                {
                    pairs.Add(new Pair(i, 0));
                }
                else if (source[i] == ')')
                {
                    for (int j = pairs.Count - 1; j >= 0; j--)
                    {
                        if (pairs[j].end == 0)
                        {
                            Pair pair = pairs[j];
                            pair.end = i;
                            break;
                        }
                    }
                }
            }            for (int i = pairs.Count - 1; i >= 0; i--)
            {
                Pair pair = pairs[i];
                Console.WriteLine(source.Substring(pair.begin + 1, pair.end - pair.begin -1 ));
            }        }

Answer 2

            string aa = "bus(van(suv)pickup)car(truck)";            string[] bb = aa.Split('(');            string cc = "";
            for (int i = 0; i < bb.Length; i++)
            {
                cc += bb[i]+",";
                
            }            string[] dd = cc.Split(')');
            string ee = dd[0];            for (int i = 1; i < dd.Length; i++)
            {
                ee += "," + dd[i];
            }            string[] ff = ee.Split(',');            for (int i = 0; i < ff.Length; i++)
            {
                Console.WriteLine(ff[i]);
            }                Console.ReadLine();

Answer 3

完全按照lz要求进行排序的代码，不需要depth成员:
 class Pair
        {
            public Pair(int begin, int end)
            {
                this.begin = begin;
                this.end = end;
            }
            public int begin;
            public int end;
        }        private void button2_Click(object sender, EventArgs e)
        {            
            string source = "bus(van(suv)pickup)car(truck)";
            List<Pair> pairs = new List<Pair>();
            for (int i = 0; i<source.Length; ++i)
            {
                if (source[i] == '(')
                {
                    pairs.Add(new Pair(i, 0));                    
                }
                else if (source[i] == ')')
                {
                    for (int j = pairs.Count - 1; j >= 0; j--)
                    {
                        if (pairs[j].end == 0)
                        {
                            Pair pair = pairs[j];
                            pair.end = i;
                            break;
                        }
                    }
                }
            }            pairs.Sort(delegate(Pair a, Pair b)  
            {
              
                if ((a.begin < b.begin) && (a.end > b.end))
                {
                    return 1;
                }
                else
                {
                    if ((a.begin > b.begin) && (a.end < b.end))
                    {
                        return -1;
                    }
                    return a.begin < b.begin ? -1 : 1;
                }            
            });            foreach (Pair pair in pairs)
            {
                Console.WriteLine(source.Substring(pair.begin + 1, pair.end - pair.begin -1 ));
            }            Console.WriteLine(source);                   }

Answer 4

List<string> tlist = new List<string>();
            Stack<string> Resultlist = new Stack<string>();
            string strContent = "bus(van(suv)pickup)car(truck)"; string strtempContent = "";
            Regex re = new Regex(@"\((?<info>[^\(\)]*(((?'Open'\()[^\(\)]*)+((?'-Open'\))[^\(\)]*)+)*(?(open)(?!)))\)");
            tlist.Add(strContent);
            while (tlist.Count > 0)
            {
                strtempContent = tlist[0];
                Resultlist.Push(strtempContent);
                tlist.RemoveAt(0);
                foreach (Match m in re.Matches(strtempContent))
                {
                    tlist.Insert(0, m.Groups["info"].Value.Trim());
                }
            }            while (Resultlist.Count > 0)
            {
                tlist.Add(Resultlist.Pop());
            }
tlist 就是结果，多次测试一下，特多是比较复杂的情况下。思路就是如此。

Answer 5

当然while循环里面可以替换为栈

Answer 6

仿照8楼用栈写了一个，这样就不用反复回溯了，有点偷懒，用了KeyValuePairusing System;
using System.Collections.Generic;namespace ConsoleApplication4
{
    class Program
    {
        class Pair
        {
            public int StartIndex;
            public int EndIndex;
            public Pair(int start, int end) { StartIndex = start; EndIndex = end; }            public void Write(string str)
            {
                for (int i = StartIndex; i <= EndIndex; i++)
                    Console.Write(str[i]);
                Console.WriteLine();
            }
        }        static void Main(string[] args)
        {
            string  content = "(bus(van(suv)pickup)car(truck))";
            Stack<KeyValuePair<char, int>> stack = new Stack<KeyValuePair<char, int>>();
            KeyValuePair<char, int> key = new KeyValuePair<char, int>((char)0, 0);
            List<Pair> outPut = new List<Pair>();            for (int i = 0; i < content.Length; i++)
            {
                stack.Push(new KeyValuePair<char,int>(content[i],i));
                
                if (content[i] == ')')
                {
                    do { key = stack.Pop(); }
                    while (stack.Count > 0 && key.Key != '(');
                    outPut.Add(new Pair(key.Value + 1, i - 1));
                }
            }            outPut.Add(new Pair(0, content.Length - 1));            foreach (Pair item in outPut)
                item.Write(content);
        }
    }
}

Answer 7

不考虑可读性，只追求精简的话，这样也行
using System;
using System.Collections.Generic;namespace ConsoleApplication4
{
    class Program
    {
        static void Main(string[] args)
        {
            string  content = "(bus(van(suv)pickup)car(truck))";
            Stack<KeyValuePair<char, int>> stack = new Stack<KeyValuePair<char, int>>();
            KeyValuePair<char, int> key = new KeyValuePair<char, int>((char)0, 0);            for (int i = 0; i < content.Length; i++)
            {
                stack.Push(new KeyValuePair<char,int>(content[i],i));
                
                if (content[i] == ')')
                {
                    do { key = stack.Pop(); }
                    while (stack.Count > 0 && key.Key != '(');
                    Console.WriteLine(content.Substring(key.Value + 1,i - key.Value - 1));
                }
            }            Console.WriteLine(content);
        }
    }
}

Answer 8

嗯，用Stack更好一点，看起来对net类库还是不太熟。