C#堆栈

2022-07-15 80酷酷网 80kuku.com

using System;

namespace ZH.DataFrame.AbstractData
{
    ObjectStackADT object堆栈#region ObjectStackADT object堆栈
    /**//// <summary>
    /// object堆栈(先进后出)
    /// </summary>
    public class StackADT
    {
        private object[] s;
        private int N;
        public StackADT(int maxN)
        {
            s=new object[maxN];N=0;
        }
        public bool isEmpty()
        {
            return (N==0);
        }
        /**//// <summary>
        /// 推入
        /// </summary>
        /// <param name="item"></param>
        public void push(object item)
        {
            s[N++]=item;
        }
        /**//// <summary>
        /// 推出
        /// </summary>
        /// <returns></returns>
        public object pop()
        {
            object t=s[--N];
            s[N]=null;
            return t;
        }

}
#endregion

    NodeStack(int) 链表int堆栈#region NodeStack(int) 链表int堆栈
/**//// <summary>
/// 链表int堆栈
/// </summary>
    public class NodeStack
    {

        private class Node
        {
            public int item;public Node next;
            public Node(int item1,Node next)
            {
                item=item1;this.next=next;
            }
        }
        private Node head;
        public NodeStack()
        {
            head=null;
        }
        public bool isEmpty()
        {
           return (head==null);
        }
        public void push(int item)
        {
            head=new Node(item,head);
        }
        public int pop()
        {
            int v=head.item;
            Node t=head.next;
            head=t;
            return v;
        }
    }
    #endregion

    NodeStack(Object) 链表Object堆栈#region NodeStack(Object) 链表Object堆栈
/**//// <summary>
/// 链表Object堆栈
/// </summary>
    public class ONodeStack
    {

        private class Node
        {
            public object item;public Node next;
            public Node(object item1,Node next)
            {
                item=item1;this.next=next;
            }
        }
        private Node head;
        public ONodeStack()
        {
            head=null;
        }
        public bool isEmpty()
        {
            return (head==null);
        }
        public void push(object item)
        {
            head=new Node(item,head);
        }
        public object pop()
        {
            object v=head.item;
            Node t=head.next;
            head=t;
            return v;
        }
    }
    #endregion

    DoubleStack Double堆栈#region DoubleStack Double堆栈
    /**//// <summary>
    /// Double堆栈
    /// </summary>
    public class intStack
    {
        private double[] s;
        private int N;
        public intStack(int maxN)
        {
            s=new double[maxN];N=0;
        }
        public bool isEmpty()
        {
            return N==0;
        }
        public void push(double item)
        {
            s[N++]=item;
        }
        public double pop()
        {
            return s[--N];
        }

    }
    #endregion

    charStack 字符堆栈#region charStack 字符堆栈
    /**//// <summary>
    /// 字符堆栈
    /// </summary>
    public class charStack
    {
        private char[] ss;
        private int N;
        public charStack(int maxN)
        {
            ss=new char[maxN];N=0;
        }
        public bool isEmpty()
        {
            return N==0;
        }
        public void push(char item)
        {
            ss[N++]=item;
        }
        public char pop()
        {
            return ss[--N];
        }
    }
    #endregion

    InfixToPostfix 中缀法转后缀法#region InfixToPostfix 中缀法转后缀法
    /**//// <summary>
    /// 中缀法转后缀法
    /// </summary>
    public class InfixToPostfix
    {
        public static char[] GetInfixToPostfix(string str)
        {
            char[] a=str.ToCharArray();
            int N=a.Length;
            charStack s=new charStack(N);
            char[] b=new char[2*Tonum(a)];
            int n=0;
            for(int i=0;i<N;i++)
            {

                if(a[i]==')')
                {
                    b[n++]=' ';
                    b[n++]=s.pop();

                }
                if((a[i]=='+')||(a[i]=='*')||(a[i]=='-')||(a[i]=='/'))
                    s.push(a[i]);
                if((a[i]>='0')&&(a[i]<='9')||a[i]=='.')
                {
                    if((a[i-1]>='0')&&(a[i-1]<='9')||a[i-1]=='.')
                    {
                        b[n++]=a[i];
                    }
                    else
                    {
                        b[n++]=' ';
                        b[n++]=a[i];

                    }
                }

            }
            return b;
        }
        private static int Tonum(char[] c)
        {
            int index=c.Length;
            int index1=c.Length;
            for(int i=0;i<index;i++)
            {
                if((c[i]=='(')||(c[i]==')'))
                {
                    index1=index1-1;
                }
            }
            return index1;
        }
    }
    #endregion

    Postfix 计算中缀法表达式#region Postfix 计算中缀法表达式
    /**//// <summary>
    /// 计算中缀法表达式
    /// </summary>
    public class Postfix
    {
        public static double GetStringPostfix(string str)
        {
            char[] a= str.ToCharArray();
            int N=a.Length;
            intStack s=new intStack(N);

            for(int i=0;i<N;i++)
            {
                if(a[i]=='+')
                {
                    s.push(s.pop()+s.pop());
                }
                if(a[i]=='-')
                {
                    double num1=s.pop();
                    double num2=s.pop();

                    s.push(num2-num1);
                }
                if(a[i]=='/')
                {
                    double num1=s.pop();
                    double num2=s.pop();
                    s.push(num2/num1);
                }

                if(a[i]=='*')
                    s.push(s.pop()*s.pop());
                if((a[i]>='0')&&(a[i]<='9'))//(0)防止s.pop索引超界
                    s.push(0);
                while((a[i]>='0')&&(a[i]<='9'))//计算合并多余两位的数字
                {

                    s.push(10*s.pop()+(a[i++]-'0'));//a[i++]-'0'把字符转化为数字
                }
                a[i]=='.'#region a[i]=='.'
                if(a[i]=='.')
                {

                    double num1=s.pop();
                    i=i+1;
                    string f=null;
                    while((a[i]>='0')&&(a[i]<='9'))
                    {
                        f=f+a[i++];
                    }
                    int n=f.Length;
                    double nf=Convert.ToInt32(f);
                    for(int j=0;j<n;j++)
                    {
                        nf=0.1*nf;
                    }
                    s.push(num1+nf);
                }
                #endregion

            }
            return s.pop();
        }
        public static double GetCharPostfix(char[] ch)
        {
            char[] a= ch;
            int N=a.Length;
            intStack s=new intStack(N);

}