using System;

​

public class Program

{

    // -----------------------------------------

    // 1) Constants for token types (no 'enum')

    // -----------------------------------------

    const int TOKEN_NUMBER  = 1;  // e.g. "3"

    const int TOKEN_OP      = 2;  // e.g. "+", "-", "*", "/"

    const int TOKEN_LPAREN  = 3;  // "("

    const int TOKEN_RPAREN  = 4;  // ")"

​

    // -----------------------------------------

    // 2) Arrays to store tokens

    // -----------------------------------------

    static int[] tokenTypes    = new int[100];  // will hold 1, 2, 3, or 4

    static string[] tokenTexts = new string[100]; // e.g. "3", "+", "*", "("

    static int tokenCount = 0;

​

    // -----------------------------------------

    // 3) Constants for node types

    // -----------------------------------------

    const int NODE_NUMBER  = 1;  // e.g. "3"

    const int NODE_OPERATOR= 2;  // e.g. "+", "*"

​

    // -----------------------------------------

    // 4) Arrays to represent our "tree" nodes

    // -----------------------------------------

    static int[]    nodeTypes  = new int[100];   // 1 or 2

    static string[] nodeValues = new string[100];// "3", "+", etc.

    static int[]    leftChild  = new int[100];   // index of left child (or -1 if none)

    static int[]    rightChild = new int[100];   // index of right child (or -1 if none)

    static int nodeCountGlobal = 0;

​

    // We'll also use arrays for the "stack" used in building the tree.

    static int[] stackArray    = new int[100]; 

    static int stackTop        = -1; // means empty stack

​

    // We'll use arrays for the "stack" used in the shunting yard, too.

    static int[] opStackTypes  = new int[100];

    static string[] opStackText= new string[100];

    static int opStackTop      = -1;

​

    public static void Main()

    {

        // Try changing this expression if you like:

        string expression = "3+4*5";

        Console.WriteLine("Expression: " + expression);

​

        // 1. Tokenize (iterative)

        Tokenize(expression);

        Console.WriteLine("\nTokens:");

        for (int i = 0; i < tokenCount; i++)

        {

            Console.WriteLine($"  Type={tokenTypes[i]}, Text='{tokenTexts[i]}'");

        }

​

        // 2. Convert to postfix (shunting yard, iterative)

        // We'll store the output in an array for postfix tokens.

        int[] postfixTypes = new int[100];

        string[] postfixTexts = new string[100];

        int postfixCount = ConvertToPostfix(postfixTypes, postfixTexts);

​

        // Let's print the postfix form to see it

        Console.WriteLine("\nPostfix tokens:");

        for (int i = 0; i < postfixCount; i++)

        {

            Console.Write(postfixTexts[i] + " ");

        }

        Console.WriteLine();

​

        // 3. Build a tree from the postfix tokens (iterative)

        //    We'll get back the index of the root node.

        int rootIndex = BuildTreeFromPostfix(postfixTypes, postfixTexts, postfixCount);

​

        // 4. Print the tree in a breadth-first way (iterative queue)

        Console.WriteLine("\nTree (breadth-first):");

        PrintTreeBreadthFirst(rootIndex);

    }

​

    // ----------------------------------------------------------

    // 1) Tokenize the input string (no objects, no recursion)

    // ----------------------------------------------------------

    static void Tokenize(string expr)

    {

        tokenCount = 0;

        for (int i = 0; i < expr.Length; i++)

        {

            char c = expr[i];

​

            if (char.IsDigit(c))

            {

                // Gather full number (in case it's more than one digit, like 123)

                int startPos = i;

                while (i+1 < expr.Length && char.IsDigit(expr[i+1]))

                {

                    i++;

                }

                // The substring from startPos to i is our number

                string numberText = expr.Substring(startPos, (i - startPos + 1));

                tokenTypes[tokenCount] = TOKEN_NUMBER;

                tokenTexts[tokenCount] = numberText;

                tokenCount++;

            }

            else if (c == '+' || c == '-' || c == '*' || c == '/')

            {

                tokenTypes[tokenCount] = TOKEN_OP;

                tokenTexts[tokenCount] = c.ToString();

                tokenCount++;

            }

            else if (c == '(')

            {

                tokenTypes[tokenCount] = TOKEN_LPAREN;

                tokenTexts[tokenCount] = "(";

                tokenCount++;

            }

            else if (c == ')')

            {

                tokenTypes[tokenCount] = TOKEN_RPAREN;

                tokenTexts[tokenCount] = ")";

                tokenCount++;

            }

            else

            {

                // We ignore spaces or unknown chars

            }

        }

    }

​

    // ----------------------------------------------------------

    // 2) Convert tokens to postfix (Shunting Yard, iterative)

    // ----------------------------------------------------------

    static int ConvertToPostfix(int[] outTypes, string[] outTexts)

    {

        int outCount = 0;

        opStackTop = -1;

​

        for (int i = 0; i < tokenCount; i++)

        {

            int tType = tokenTypes[i];

            string tText = tokenTexts[i];

​

            if (tType == TOKEN_NUMBER)

            {

                // numbers go straight to output

                outTypes[outCount] = tType;

                outTexts[outCount] = tText;

                outCount++;

            }

            else if (tType == TOKEN_OP)

            {

                // pop from operator stack while top is an operator of higher/equal precedence

                // or until left parenthesis

                while (opStackTop >= 0 && opStackTypes[opStackTop] == TOKEN_OP &&

                       GetPrecedence(opStackText[opStackTop]) >= GetPrecedence(tText))

                {

                    outTypes[outCount] = opStackTypes[opStackTop];

                    outTexts[outCount] = opStackText[opStackTop];

                    outCount++;

                    opStackTop--;

                }

                // push current operator

                opStackTop++;

                opStackTypes[opStackTop] = tType;

                opStackText[opStackTop] = tText;

            }

            else if (tType == TOKEN_LPAREN)

            {

                // push '(' onto stack

                opStackTop++;

                opStackTypes[opStackTop] = tType;

                opStackText[opStackTop] = tText;

            }

            else if (tType == TOKEN_RPAREN)

            {

                // pop until '('

                while (opStackTop >= 0 && opStackTypes[opStackTop] != TOKEN_LPAREN)

                {

                    outTypes[outCount] = opStackTypes[opStackTop];

                    outTexts[outCount] = opStackText[opStackTop];

                    outCount++;

                    opStackTop--;

                }

                // pop the '(' itself

                if (opStackTop >= 0 && opStackTypes[opStackTop] == TOKEN_LPAREN)

                {

                    opStackTop--;

                }

            }

        }

​

        // pop remaining operators

        while (opStackTop >= 0)

        {

            outTypes[outCount] = opStackTypes[opStackTop];

            outTexts[outCount] = opStackText[opStackTop];

            outCount--;

            outCount++;

            opStackTop--;

        }

​

        return outCount;

    }

​

    // Precedence function (higher number = higher precedence)

    static int GetPrecedence(string op)

    {

        if (op.Equals("*") || op.Equals("/")) return 2;

        if (op.Equals("+") || op.Equals("-")) return 1;

        return 0;

    }

​

    // ----------------------------------------------------------

    // 3) Build a tree from postfix (iterative stack)

    // ----------------------------------------------------------

    static int BuildTreeFromPostfix(int[] pTypes, string[] pTexts, int pCount)

    {

        stackTop = -1;

        nodeCountGlobal = 0;

​

        for (int i = 0; i < pCount; i++)

        {

            int tType = pTypes[i];

            string tText = pTexts[i];

​

            if (tType == TOKEN_NUMBER)

            {

                // create a node for the number

                int nIndex = CreateNode(NODE_NUMBER, tText, -1, -1);

                // push node index on stack

                stackTop++;

                stackArray[stackTop] = nIndex;

            }

            else if (tType == TOKEN_OP)

            {

                // pop two nodes for right and left

                int rightIndex = stackArray[stackTop];

                stackTop--;

                int leftIndex = stackArray[stackTop];

                stackTop--;

​

                // create an operator node

                int nIndex = CreateNode(NODE_OPERATOR, tText, leftIndex, rightIndex);

​

                // push the new node index on stack

                stackTop++;

                stackArray[stackTop] = nIndex;

            }

        }

​

        // the final node on the stack is our root

        return stackArray[stackTop];

    }

​

    static int CreateNode(int t, string val, int left, int right)

    {

        nodeTypes[nodeCountGlobal]  = t;

        nodeValues[nodeCountGlobal] = val;

        leftChild[nodeCountGlobal]  = left;

        rightChild[nodeCountGlobal] = right;

​

        nodeCountGlobal++;

        return nodeCountGlobal - 1;

    }

​

    // ----------------------------------------------------------

    // 4) Print the tree (breadth-first, iterative)

    // ----------------------------------------------------------

    static void PrintTreeBreadthFirst(int rootIndex)

    {

        if (rootIndex < 0) return;

​

        // We'll use a simple queue. We'll store up to 100 node indices.

        int[] queue = new int[100];

        int queueStart = 0;

        int queueEnd = 0;

​

        // Enqueue the root

        queue[queueEnd] = rootIndex;

        queueEnd++;

​

        while (queueStart < queueEnd)

        {

            int current = queue[queueStart];

            queueStart++;

​

            // Print current node

            Console.WriteLine(

                $"NodeIndex={current}, " +

                $"Type={(nodeTypes[current] == NODE_NUMBER ? "NUMBER" : "OPERATOR")}, " +

                $"Value='{nodeValues[current]}', " +

                $"Left={leftChild[current]}, Right={rightChild[current]}"

            );

​

            // Enqueue children if they exist

            if (leftChild[current] != -1)

            {

                queue[queueEnd] = leftChild[current];

                queueEnd++;

            }

            if (rightChild[current] != -1)

            {

                queue[queueEnd] = rightChild[current];

                queueEnd++;

            }

        }

    }

}

​