using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;

namespace Biff8Excel.Formulas
{
    public class ReversePolishNotation
    {
        string Op;
        ushort CurLevel;
        ushort Level;

        string[] OpStack = new string[501];
        ushort[] LevelStack = new ushort[501];
        ushort StackTop;
        List<string> m_Result;

        bool init = false;

        public ReversePolishNotation()
        {
            //StackTop = -1;

            //StackTop = 0;
            //init = false;
        }

        void Push(string op, ushort level)
        {
            //StackTop++;
            OpStack[StackTop] = op;
            LevelStack[StackTop] = level;

            StackTop++;
        }

        bool Pop() 
        {
            //if (StackTop == -1)
            //    return false;

            if (!init)
                return false;

            Op = OpStack[StackTop];
            Level = LevelStack[StackTop];
            StackTop--;
            return true;
        }

        public List<string> ConverToReversePolishNotation(List<string> expressions)
        {            
            string CurOp;
            m_Result = new List<string>();

            //StackTop = -1;
            StackTop = 0;
            init = false;

            for (int i = 0; i < expressions.Count; i++)
            {
                CurOp = expressions[i];

                if (CurOp == "+" || CurOp == "-")
                {
                    while (Pop())
                    {
                        if (Level == CurLevel )
                        {
                            m_Result.Add(Op);
                        }
                        else
                        {
                            Push(Op,Level);
                            break;
                        }
                    }

                    Push( CurOp,CurLevel);

                }
                else if (CurOp == "*" || CurOp == "/")
                {
                    while (Pop())
                    {
                        if (Level == CurLevel && Op == "^")
                        {
                            m_Result.Add(Op);
                        }
                        else
                        {
                            Push(Op, Level);
                            break;
                        }
                    }
                    Push(CurOp, CurLevel);
                }
                else if (CurOp == "^")
                {
                    Push(CurOp, CurLevel);
                }
                else if (CurOp == "(")
                {
                    CurLevel++;
                }
                else if (CurOp == ")")
                {
                    while (Pop())
                    {
                        if (Level == CurLevel)
                        {
                            m_Result.Add(Op);
                        }
                        else
                        {
                            Push(Op, Level);
                            break;
                        }
                    }
                    CurLevel--;
                }
                else if (CurOp == " ")
                {
                    // Ignore Space
                }
                else
                {
                    m_Result.Add(CurOp);
                }
            }

            while (Pop())
            {
                m_Result.Add(Op);
            }

            return m_Result;
        }

    }
}