天天看點

C#資料結構與算法系列(九):棧實作綜合電腦(中綴表達式)

1.問題介紹

C#資料結構與算法系列(九):棧實作綜合電腦(中綴表達式)

 2.實作思路

C#資料結構與算法系列(九):棧實作綜合電腦(中綴表達式)

 3.代碼實作

第一個版本(采用這個)

public class ArrayStack
    {
        private int _maxSize;
        private int[] _arr;
        private int _top = -1;

        /// <summary>
        /// 初始化棧
        /// </summary>
        /// <param name="maxSize"></param>
        public ArrayStack(int maxSize)
        {
            _maxSize = maxSize;
            _arr = new int[_maxSize];
        }

        /// <summary>
        /// 棧是否為空
        /// </summary>
        /// <returns></returns>
        public bool IsEmpty() => _top == -1;

        /// <summary>
        /// 棧是否滿
        /// </summary>
        /// <returns></returns>
        public bool IsFull() => _top == _maxSize-1;

        /// <summary>
        /// 入棧
        /// </summary>
        /// <param name="value"></param>
        public void Push(int value)
        {
            if (IsFull())
            {
                Console.WriteLine("棧滿");
            }
            else
            {
                _top++;
                _arr[_top] = value;
            }
        }
       /// <summary>
       /// 出棧
       /// </summary>
       /// <returns></returns>
        public int Pop()
        {
            if (IsEmpty())
            {
                throw new Exception("棧空");
            }
            int value = _arr[_top];

            _top--;

            return value;
        }

        /// <summary>
        /// 棧清單
        /// </summary>
        public void List()
        {
            if (IsEmpty())
            {
                Console.WriteLine("棧空");
            }
            else
            {
                for (int i = _top; i >= 0; i--)
                {
                    Console.WriteLine($"stack:[{i}]={_arr[i]}");
                }
            }
        }

        /// <summary>
        /// 傳回目前棧頂的值
        /// </summary>
        /// <returns></returns>
        public int Peek() => _arr[_top];

        /// <summary>
        /// 優先級判斷
        /// </summary>
        /// <param name="oper"></param>
        /// <returns></returns>
        public int Priority(int oper)
        {
            if (oper == '*' || oper == '/')
            {
                return 1;
            }
            else if (oper == '+' || oper == '-')
            {
                return 0;
            }
            else return -1;
        }
        /// <summary>
        /// 計算
        /// </summary>
        /// <param name="num1"></param>
        /// <param name="num2"></param>
        /// <param name="oper"></param>
        /// <returns></returns>
        public int Cal(int num1, int num2, int oper)
        {
            int result = 0;
            switch (oper)
            {
                case '+':
                    result = num1 + num2;
                    break;
                case '-':
                    result = num2 - num1; //注意順序
                    break;
                case '*':
                    result = num1 * num2;
                    break;
                case '/':
                    result = num2 / num1; //注意順序
                    break;
                default:
                    break; 
            }
            return result;
        }

        /// <summary>
        /// 判斷是否是操作符
        /// </summary>
        /// <param name="val"></param>
        /// <returns></returns>
        public bool IsOper(char val)
        {
            return val == '-' || val == '+' || val == '*' || val == '/';
        }
   }      
using System;


namespace DataStructure
{
    public class Calculator
    {
        public static void Test()
        {
            string expression = "300+2*3+2-1";

            ArrayStack numStack = new ArrayStack(10);

            ArrayStack operStack = new ArrayStack(10);

            //把字元串轉換成char數組
            char[] arr = expression.ToCharArray();

            /*
                public unsafe char[] ToCharArray()
             
                 int length = this.Length;
                 char[] array = new char[length];
                 if (length > 0)
                 {
                     fixed (char* ptr = &this.m_firstChar)
                     {
                         fixed (char* ptr2 = array)
                         {
                             string.wstrcpy(ptr2, ptr, length);
                         }
                     }
                 }
                 return array;
              
             */
            //結果
            int result = 0;

            int num1 = 0;

            int num2 = 0;

            int oper = 0;

            string keepNum = "";

            for (int i = 0; i < arr.Length; i++)
            {
                //判斷是不是操作符
                if (operStack.IsOper(arr[i]))
                {
                    //如果不是空的
                    if (!operStack.IsEmpty())
                    {
                        //如果符号棧中有操作符,就進行比較,如果目前操作符的優先級小于或等于棧中的操作符,就需要從棧中pop出兩個數
                        //再從符号棧中pop出一個符号,進行運算,将得到結果,入數棧,然後再把目前操作符入符号棧
                        if (operStack.Priority(arr[i]) <= operStack.Priority(operStack.Peek()))
                        {
                            num1 = numStack.Pop();

                            num2 = numStack.Pop();

                            oper = operStack.Pop();

                            //計算
                            result = numStack.Cal(num1, num2, oper);

                            numStack.Push(result);

                            operStack.Push(arr[i]);
                        }
                        else
                        {
                            //如果目前操作符的優先級大于棧中的操作符就直接入符号棧
                            operStack.Push(arr[i]);
                        }
                    }
                    else
                    {
                        //為空就直接入符号棧
                        operStack.Push(arr[i]);
                    }
                }
                else
                {
                    //把字元轉成字元串
                    keepNum += arr[i];


                    for (int j = i + 1; j < arr.Length; j++)
                    {
                        //判斷arr[i]的面是否是操作符 如果不是則拼接
                        if (!numStack.IsOper(arr[j]))
                        {
                            keepNum += arr[j];

                            i++;//當确定後一個是數字的時候 索引也要跟着往後移
                        }
                        //如果是則終止
                        else break;
                    }

                    numStack.Push(int.Parse(keepNum));

                    //一定要置空,否則會保留上一次操作
                    keepNum = "";
                }
            }
            //當數字占和符号棧都不為空的情況下才進循環
            while (!operStack.IsEmpty() && !numStack.IsEmpty())
            {
                //當符号棧為空的時候就跳出循環
                if (operStack.IsEmpty()) break;

                num1 = numStack.Pop();

                num2 = numStack.Pop();

                oper = operStack.Pop();

                result = numStack.Cal(num1, num2, oper);

                numStack.Push(result);
            }

            Console.WriteLine($"表達式{expression}={numStack.Pop()}");
        }
    }
}      

第二個版本

public class ArrayStack {
    private int maxSize;
    private int[] stack;
    private int top = -1;

    public ArrayStack(int maxSize) {
        this.maxSize = maxSize;
        stack = new int[maxSize];
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public boolean isFull() {
        return top == maxSize;
    }

    public void push(int value) {
        if (isFull()) {
            System.out.println("棧已滿!");
        } else {
            top++;
            stack[top] = value;
        }
    }

    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("棧為空");
        }
        int result = stack[top];
        top--;
        return result;
    }

    public void list() {
        if (isEmpty()) {
            System.out.println("棧為空");
        } else {
            for (int i = top; i >= 0; i--) {
                System.out.printf("stack[%d]=%d\n", i, stack[i]);
            }
        }
    }

    public int peek() {

            return stack[top];
    }

    public boolean isOperate(int vaule) {
        return vaule == '*' || vaule == '/' || vaule == '+' || vaule == '-';
    }

    public int calculate(int num1, int num2, int operate) {
        switch (operate) {
            case '*':
                return num1 * num2;
            case '/':
                return num2 / num1;
            case '+':
                return num1 + num2;
            case '-':
                return num2 - num1;
            default:
                return 0;
        }
    }

    public int priority(int operate) {
        if (operate == '*' || operate == '/') {
            return 1;
        } else if (operate == '+' || operate == '-') {
            return 0;
        } else return -1;
    }
}      
public class Calculator {
    public static void main(String[] args) {
        String expression = "3+2*5-1";

        ArrayStack numStack = new ArrayStack(10);

        ArrayStack operateStack = new ArrayStack(10);

        int num1, num2, operate, result;

        int index = num1 = num2 = operate = result = 0;

        char value;

        while (true) {

            value = expression.substring(index, index + 1).charAt(0);


            if (operateStack.isOperate(value)) {
                if (operateStack.isEmpty()) {
                    operateStack.push(value);
                } else {
                    if (operateStack.priority(value) <= operateStack.priority(operateStack.peek())) {

                        num1 = numStack.pop();

                        num2 = numStack.pop();

                        operate = operateStack.pop();

                        result = operateStack.calculate(num1, num2, operate);

                        numStack.push(result);

                        operateStack.push(value);
                    } else {
                        operateStack.push(value);
                    }
                }
            } else {
                String keepNum = "" + value;

                if (index == expression.length() - 1) {

                    numStack.push(Integer.parseInt(keepNum));

                    break;
                } else {

                    char nextNum = expression.substring(index + 1, index + 2).charAt(0);

                    if (operateStack.isOperate(nextNum)) {

                        numStack.push(Integer.parseInt(keepNum));
                    } else {

                        keepNum += nextNum;

                        numStack.push(Integer.valueOf(keepNum));

                        keepNum = "";
                    }
                }
            }

            index++;
        }

        while (true) {

            if (operateStack.isEmpty()) {
                break;
            }
            num1 = numStack.pop();

            num2 = numStack.pop();

            operate = operateStack.pop();

            result = operateStack.calculate(num1, num2, operate);

            numStack.push(result);
        }

        System.out.printf("\n%s的結果是%d", expression, numStack.pop());
    }
}