仿 SQL 查詢分析器的 C# 計算器（十四）：語法分析堆疊演算法完整實作與 SyntaxTreeAnalyse 類別

12. 堆疊分析結束處理

列表分析結束時堆疊不為空，需對堆疊處理。經過堆疊分析，遵循「高出低入」原則，堆疊中的 TokenRecord 肯定是棧底優先級最低、棧頂最高。只需依次彈棧，加入新棧頂的 ChildList 中。最後彈出的 TokenRecord 即整棵樹的根節點，作為傳回值。至此堆疊為空，獲得預期樹狀圖，回傳根節點。

完整代碼實作

語法分析放在獨立檔案 SyntaxTreeAnalyse.cs，僅含 SyntaxTreeAnalyse 類別，專門分析語法樹。唯一公開入口 SyntaxTreeGetTopTokenAnalyse，傳入 TokenRecord 清單，分析後回傳頂層 TokenRecord（樹根）。具體代碼：

internal class SyntaxTreeAnalyse
{
    internal static TokenRecord SyntaxTreeGetTopTokenAnalyse(List<TokenRecord> TokenList, int IndexStart, int IndexEnd)
    {
        int intIndexCurrent = IndexStart, intIndexSubStart = IndexStart;
        TokenRecord Token;
        Stack<TokenRecord> StackCompart = new Stack<TokenRecord>();
        Stack<TokenRecord> StackOperate = new Stack<TokenRecord>();

        for (int intIndex = IndexStart; intIndex <= IndexEnd; intIndex++)
        {
            Token = TokenList[intIndex]; intIndexCurrent = intIndex;
            if (Token is TokenLeftBracket)
            {
                StackCompart.Push(TokenList[intIndexCurrent]);
                intIndexSubStart = intIndexCurrent + 1;
                while (StackCompart.Count > 0)
                {
                    intIndexCurrent += 1;
                    if (intIndexCurrent >= TokenList.Count) throw new SyntaxException(Token.Index, Token.Length, "缺少配對的括號");
                    if (TokenList[intIndexCurrent] is TokenLeftBracket) StackCompart.Push(TokenList[intIndexCurrent]);
                    else if (TokenList[intIndexCurrent] is TokenRightBracket) StackCompart.Pop();
                }
                TokenRecord TokenInnerTop = SyntaxTreeGetTopTokenAnalyse(TokenList, intIndexSubStart, intIndexCurrent - 1);
                if (TokenInnerTop != null) Token.ChildList.Add(TokenInnerTop);
                else throw new SyntaxException(Token.Index, Token.Length, "括號內不包含計算運算式");
                intIndex = intIndexCurrent;
                SyntaxTreeStackAnalyse(StackOperate, Token);
            }
            else if (Token is TokenMethod)
            {
                if (intIndexCurrent >= IndexEnd || !(TokenList[intIndexCurrent + 1] is TokenLeftBracket))
                    throw new SyntaxException(Token.Index, Token.Length, "方法後缺少括號");
                intIndexSubStart = intIndexCurrent; intIndexCurrent += 1;
                StackCompart.Push(TokenList[intIndexCurrent]);
                while (StackCompart.Count > 0)
                {
                    intIndexCurrent += 1;
                    if (intIndexCurrent >= TokenList.Count) throw new SyntaxException(Token.Index, Token.Length, "缺少配對的括號");
                    if (TokenList[intIndexCurrent] is TokenLeftBracket) StackCompart.Push(TokenList[intIndexCurrent]);
                    else if (TokenList[intIndexCurrent] is TokenRightBracket) StackCompart.Pop();
                }
                if ((intIndexCurrent - intIndexSubStart) == 2)
                    throw new SyntaxException(TokenList[intIndexCurrent - 1].Index, 1, "括號內不包含計算運算式");
                SyntaxTreeMethodAnalyse(TokenList, intIndexSubStart, intIndexCurrent);
                intIndex = intIndexCurrent;
                SyntaxTreeStackAnalyse(StackOperate, Token);
            }
            else if (Token is TokenSymbol || Token is TokenValue)
                SyntaxTreeStackAnalyse(StackOperate, Token);
            else
                throw new SyntaxException(Token.Index, Token.Length, "運算子位置錯誤");
        }
        return SyntaxTreeStackGetTopToken(StackOperate);
    }

    private static void SyntaxTreeMethodAnalyse(List<TokenRecord> ListToken, int IndexStart, int IndexEnd)
    {
        int intIndexSubStart = IndexStart + 2, intIndexSubEnd = IndexEnd;
        TokenRecord TokenMethod = ListToken[IndexStart];
        TokenRecord TokenCurrent;
        Stack<TokenRecord> StackCompart = new Stack<TokenRecord>();
        for (int intIndex = IndexStart; intIndex <= IndexEnd; intIndex++)
        {
            TokenCurrent = ListToken[intIndex];
            if (TokenCurrent is TokenLeftBracket) StackCompart.Push(TokenCurrent);
            else if (TokenCurrent is TokenRightBracket)
            {
                StackCompart.Pop();
                if (StackCompart.Count == 0)
                {
                    intIndexSubEnd = intIndex - 1;
                    TokenMethod.ChildList.Add(SyntaxTreeGetTopTokenAnalyse(ListToken, intIndexSubStart, intIndexSubEnd));
                }
            }
            else if (TokenCurrent is TokenComma)
            {
                if (StackCompart.Count == 1)
                {
                    intIndexSubEnd = intIndex - 1;
                    TokenMethod.ChildList.Add(SyntaxTreeGetTopTokenAnalyse(ListToken, intIndexSubStart, intIndexSubEnd));
                    intIndexSubStart = intIndex + 1;
                }
            }
        }
    }

    private static void SyntaxTreeStackAnalyse(Stack<TokenRecord> SyntaxTreeStack, TokenRecord NewToken)
    {
        if (SyntaxTreeStack.Count == 0) SyntaxTreeStack.Push(NewToken);
        else
        {
            if (SyntaxTreeStack.Peek().Priority < NewToken.Priority) SyntaxTreeStack.Push(NewToken);
            else
            {
                TokenRecord TempToken = null;
                while (SyntaxTreeStack.Count > 0 && SyntaxTreeStack.Peek().Priority >= NewToken.Priority)
                {
                    TempToken = SyntaxTreeStack.Pop();
                    if (SyntaxTreeStack.Count > 0)
                    {
                        if (SyntaxTreeStack.Peek().Priority >= NewToken.Priority) SyntaxTreeStack.Peek().ChildList.Add(TempToken);
                        else NewToken.ChildList.Add(TempToken);
                    }
                    else NewToken.ChildList.Add(TempToken);
                }
                SyntaxTreeStack.Push(NewToken);
            }
        }
    }

    private static TokenRecord SyntaxTreeStackGetTopToken(Stack<TokenRecord> SyntaxTreeStack)
    {
        TokenRecord TempToken = null;
        if (SyntaxTreeStack.Count > 0)
        {
            TempToken = SyntaxTreeStack.Pop();
            while (SyntaxTreeStack.Count > 0)
            { SyntaxTreeStack.Peek().ChildList.Add(TempToken); TempToken = SyntaxTreeStack.Pop(); }
        }
        return TempToken;
    }
}

代碼對括號特殊處理：遇左括號尋找配對右括號，遞歸處理該段取出頂層節點。方法也需特殊處理：必須帶括號，括號中不止一根節點，以逗號分隔依次取出節點加入方法的 ChildList，實作於 SyntaxTreeMethodAnalyse。方法間遞歸調用較易暈眩，希望有人能看懂。