using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;

namespace Exp6_3
{
    class Calculate
    {
        public static bool  checkRules(string exp) // 判断字符串是否合法
        {
            if (string.IsNullOrWhiteSpace(exp)) return false; //判断对象是否为Null和空白字符
            //去掉空格
            string noblank = Regex.Replace(exp, " ", ""); //在指定的输入字符串中，把所有匹配正则表达式模式的所有匹配的字符串替换为指定的替换字符串。

            //表达式字符串规则
            string no0 = @"[^\d\*\^\(\)+-/.]";  //不能出现运算符+-*/^、圆括号()、数字、小数点.之外的字符
            string no1 = @"^[^\d\(-]";          //开头不能是数字、左圆括号(、负号- 以外的字符
            string no2 = @"[^\d\)]$";           //结束不能是数字、右圆括号) 以外的字符
            string no3 = @"[\*\^+-/]{2}";       //+-*/^不能连续出现
            string no4 = @"[\D][.]|[.]\D";      //小数点前面或后面不能出现非数字字符
            string no5 = @"\)[\d\(]|[^\d\)]\)"; //右圆括号)后面不能出现数字、左圆括号(,前面不能出现除数字或右圆括号)以外的字符
            string no6 = @"\([^\d\(-]|[\d]\(";  //左圆括号(后面不能出现除数字、左圆括号(、负号以外的字符,前面不能出现数字
            //正则表达式中有可能出现一些与C#语言相同的字符,比如"\",会让编译器作为C#语言来识别,截断该字符串,并可能产生编译器错误
            //在该字符串前加一个"@"就是告诉编译器,这些特殊字符是作为字符串中的一部分存在的,编译器就不会去编译它了
            // ^定位点 匹配必须从字符串或一行的开头开始
            // [character_group] 匹配 character_group 中的任何单个字符。 默认情况下，匹配区分大小写。
            // [^character_group] 非：与不在 character_group 中的任何单个字符匹配 区分大小写。
            // $ 匹配必须出现在字符串的末尾或出现在行或字符串末尾的 \n 之前
            //{ n } 匹配上一个元素恰好 n 次
            
            string pattern = no0 + "|" + no1 + "|" + no2 + "|" + no3 + "|" + no4 + "|" + no5 + "|" + no6;
            if (Regex.IsMatch(noblank, pattern)) //指定的正则表达式是否在指定的输入字符串中找到匹配项，从字符串中指定的开始位置开始
            {
                return false;
            }

            //左圆括号(和右圆括号)必须成对出现
            int count = 0;
            foreach (char c in noblank)
            {
                if (c == ')')
                {
                    count++;
                    continue;
                }

                if (c == '(')
                {
                    count--;
                    continue;
                }
            }
            if (count != 0)
            {
                Console.WriteLine("左右括号不匹配");
                return false;
            }

            return true;
        }

        public static string[] toStrings(string exp) // 分割成分 把数字和其它字符分隔开
        {
            //如果要修改字符串而不创建新的对象，则可以使用System.Text.StringBuilder类
            //String声明之后在内存中大小是不可修改的，而StringBuilder可以自由扩展大小(String分配在栈区，StringBuilder分配在堆区)
            StringBuilder sb = new StringBuilder(exp);
            //去掉空格
            sb.Replace(" ", "");

            //负号与减号相同，不能与数字分开，需要特许处理：
            //1、字符串第一个"-"是负号
            //2、紧跟在"("后面的"-"是负号
            //3、如果负号后面直接跟着"("，把负号改为"-1*"。目的是把取负运算（单目运算）变成乘法运算（双目运算），免得以后要区分减法和取负。
            //4、把负号统一改为"?"			
            if (sb[0] == '-')
            {
                sb[0] = '?';
            }

            sb.Replace("(-", "(?");
            sb.Replace("?(", "?1*(");

            //添加分割符','把数字和其它字符分隔开。
            sb.Replace("+", ",+,");
            sb.Replace("-", ",-,");
            sb.Replace("*", ",*,");
            sb.Replace("/", ",/,");
            sb.Replace("(", "(,");
            sb.Replace(")", ",)");
            sb.Replace("^", ",^,");

            //分割之后，把'?'恢复成减号 '-'
            sb.Replace('?', '-');

            return sb.ToString().Split(',');
        }

        private static int getOrder(char oprator) //获取运算符的优先级
        {
            switch (oprator)
            {
                case '+':
                case '-':
                    return 1;
                case '*':
                case '/':
                    return 3;
                case '^':
                    return 5;			
                default:
                    return -1;
            }

        }


        public static string[] toRPN(string[] expStrings) // 转为后缀表达式
        {
            Stack<string> stack = new Stack<string>();
            List<string> rpn = new List<string>();
            //基本思路：
            //遍历expStrings中的字符串：
            //1、如果不是字符（即数字）就直接放到列表rpn中；
            //2、如果是字符：
            //2.1、如果stack为空，把字符压入stack中；
            //2.2、如果stack不为空，把栈中优先级大于等于该字符的运算符全部弹出(直到碰到'('或stack为空)，放到rpn中；
            //2.2 如果字符是'('，直接压入
            //2.3 如果是')'，依次弹出stack中的字符串放入rpn中，直到碰到'(',弹出并抛弃'('；

            foreach (string item in expStrings)
            {
                //1、处理"("
                if (item == "(")
                {
                    stack.Push(item);
                    continue;
                }
                //2、处理运算符 +-*/^
                if ("+-*/^".Contains(item)) // .contains() 判断一个元素内是否包含另一个元素
                {
                    if (stack.Count == 0)
                    {
                        stack.Push(item);
                        continue;
                    }
                    if (getOrder(item[0]) > getOrder(stack.Peek()[0])) // peek 不改变栈的值(不删除栈顶的值) string[0]首位 当字符看
                    {
                        stack.Push(item);
                        continue;
                    }
                    else
                    {
                        while (stack.Count > 0 && getOrder(stack.Peek()[0]) >= getOrder(item[0]) && stack.Peek() != "(")
                        {
                            rpn.Add(stack.Pop());
                        }
                        stack.Push(item);
                        continue;
                    }
                }
                //3、处理")"
                if (item == ")")
                {
                    while (stack.Peek() != "(")
                    {
                        rpn.Add(stack.Pop());
                    }
                    stack.Pop();//抛弃"("
                    continue;
                }
                //4、数据，直接放入rpn中
                rpn.Add(item);
            }
            //最后把stack中的运算符全部输出到rpn
            while (stack.Count > 0)
            {
                rpn.Add(stack.Pop());
            }
            //把字符串链表转换成字符串数组，并输出。
            return rpn.ToArray(); // 将rpn转为数组

        }

        public static double Compute(string exp)
        {
            if (!checkRules(exp))
            {
                throw new FormatException("字符串为空或不合法");
            }
            //先把字符串转换成后缀表达式字符串数组
            string[] rpn = toRPN(toStrings(exp));
            //再计算后缀表达式
            Stack<double> stack = new Stack<double>(); //存放参与计算的数值、中间值、结果	
            //算法：利用foreach来扫描后缀表达式字符串数组，得到数值则直接压入栈中，
            //得到运算符则从栈顶取出两个数值进行运算，并把结果压入栈中。最终栈中留下一个数值，为计算结果。
            foreach (string oprator in rpn)
            {
                //为什么总是弹出两个数值？因为都是双目运算。
                //先弹出的是运算符右边的数，弹出两个数值后注意运算顺序。				
                switch (oprator)
                {
                    case "+":
                        //如果读取到运算符，则从stack中取出两个数值进行运算，并把运算结果压入stack。下同。
                        stack.Push(stack.Pop() + stack.Pop());
                        break;
                    case "-":
                        stack.Push(-stack.Pop() + stack.Pop());
                        break;
                    case "*":
                        stack.Push(stack.Pop() * stack.Pop());
                        break;
                    case "/":
                        {
                            double right = stack.Pop();
                            try //一个方法使用 try 和 catch 关键字捕获异常
                            {
                                stack.Push(stack.Pop() / right);
                            }
                            catch (Exception e)
                            {
                                throw e;   //除数为0时产生异常。
                            }

                            break;
                        }
                    case "^":
                        {
                            double right = stack.Pop();
                            stack.Push(Math.Pow(stack.Pop(), right));
                            break;
                        }

                    default: //后缀表达式数组中只有运算符和数值，没有圆括号。除了运算符，剩下的就是数值了
                        stack.Push(double.Parse(oprator));  //如果读取到数值，则压入stack中
                        break;
                }
            }
            //弹出最后的计算值并返回
            return stack.Pop();
        }
    }
}