我快疯了！！！ 菜鸟求解这道编程题！！ 栈实现字符串的简单运算

Question

就是数据结构与算法  C#语言描述  栈的应用  中缀运算的改进  原先的只能实现加  现在要改 可实现加减乘除  我的思路是  改进时  字符进运算符栈时判断优先级  优先级高于运算符栈时就进栈  低时就用栈里运算符计算  描述不好~~ 这是程序：
using System;
using System.Collections;
using System.Text.RegularExpressions;namespace ConsoleApplication9
{
    class Program
    {
        static void Main(string[] args)
        {
            Stack nums = new Stack();
            Stack ops = new Stack();
            string expression = "5 + 10 * 15 + 20";
            Calculate(nums, ops, expression);
            Console.WriteLine(nums.Pop());
            Console.ReadLine();
        }
        static bool IsNumeric(string input)
        {
            bool flag = true;
            string pattern = (@"^\d+$");
            Regex validate = new Regex(pattern);
            if (!validate.IsMatch(input))
            {
                flag = false;
            }
            return flag;
        }
        static int Priority(string str)
        {
            switch (str)
            {
                case "*":
                case "/":
                    return 0;
                case "-":
                case "+":
                    return 1;
                default:
                    return 100;
            }
        }
        static void Calculate(Stack N, Stack O, string exp)
        {
            string ch, token = "";
            for (int p = 0; p <= exp.Length - 1; p++)
            {
                ch = exp.Substring(p, 1);
                if (IsNumeric(ch))
                {
                    token += ch;
                }
                if (ch == " " || p == exp.Length - 1)
                {
                    if (IsNumeric(token))
                    {
                        N.Push(token);
                        token = "";
                    }
                }
                else if (ch == "+" || ch == "-" || ch == "*" || ch == "/")
                {
                    if (O.Count == 0)
                    {
                        O.Push(ch);
                    }
                    else
                        if (Priority(O.Peek().ToString()) <= Priority(ch))
                        {
                            Compute(N, O);
                        }
                        else
                            O.Push(ch);
                }
            }
        }
        static void Compute(Stack N, Stack O)
        {
            int oper1, oper2;
            string oper;
            oper1 = Convert.ToInt32(N.Pop());
            oper2 = Convert.ToInt32(N.Pop());
            oper = Convert.ToString(O.Pop());
            switch (oper)
            {
                case "+":
                    N.Push(oper1 + oper2);
                    break;
                case "-":
                    N.Push(oper2 - oper1);
                    break;
                case "*":
                    N.Push(oper1 * oper2);
                    break;
                case "/":
                    N.Push(oper2 / oper1);
                    break;
            }
        }                
    }
}
 

Answer 1

这是我以前写的一个，就是中缀转为逆波兰，同时运算，后面那部分专门是处理优先级的，不过没怎么测试，不知道有没有Bug，算的时候最好前后加一个括号，逻辑处理比较简单using System;
using System.Collections.Generic;namespace CsdnTest
{
    class Program
    {
        static void Main(string[] args)
        {
            string exp = "((5 - 5 * 10) / 3 + 6 * (2 + 5))";
            Console.WriteLine("{0} = {1}", exp, ExpCul(exp));
            Console.ReadKey();
        }        static int ExpCul(string exp)
        {
            Stack<int> numStack = new Stack<int>();
            Stack<char> opStack = new Stack<char>();
            bool numFlag = false;            for (int i = 0; i < exp.Length; i++)
            {
                int level = CharCheckLevel(exp[i]);                if (level == 0)
                {
                    if (!numFlag)
                        numStack.Push(exp[i] - '0');
                    else
                        numStack.Push(numStack.Pop() * 10 + exp[i] - '0');
                }
                else if (level > 0)
                {
                    if (level > 2)
                    {
                        int sLevel = CharCheckLevel(opStack.Peek());
                        if (sLevel >= level && sLevel > 2)
                            numStack.Push(Cul(numStack.Pop(), numStack.Pop(), opStack.Pop()));
                        opStack.Push(exp[i]);
                    }
                    else if (level == 1)
                        opStack.Push(exp[i]);
                    else if (level == 2)
                    {
                        while (true)
                        {
                            char sign = opStack.Pop();
                            if (sign == '(') break;
                            numStack.Push(Cul(numStack.Pop(), numStack.Pop(), sign));
                        }
                    }
                }                numFlag = level == 0;
            }            return numStack.Pop();
        }        static int Cul(int newNum, int oldNum, char sign)
        {
            switch (sign)
            {
                case '+':
                    return oldNum + newNum;
                case '-':
                    return oldNum - newNum;
                case '*':
                    return oldNum * newNum;
                case '/':
                    return oldNum / newNum;
                case '%':
                    return oldNum % newNum;
                default:
                    return 0;
            }
        }        static int CharCheckLevel(char c)
        {
            if (c == '*' || c == '/' || c == '%')
                return 4;
            else if (c == '+' || c == '-')
                return 3;
            else if (c == ')')
                return 2;
            else if (c == '(')
                return 1;
            else if (c >= '0' && c <= '9')
                return 0;
            else
                return -1;
        }
    }
}

Answer 2

参考http://www.cnblogs.com/Peter-Zhang/articles/1781570.htmlusing System;
using System.Collections.Generic;
using System.Linq;
using System.Text;namespace ExpressionValue
{
    class Program
    {
        public static Boolean IsNumber(String n)
        {
            Int32 temp;
            return Int32.TryParse(n, out temp);
        }        // Get the priority of the operator, just for + - * /
        public static Int32 GetPriority(Char op)   
        {
            switch (op)
            {
                case '+':
                case '-': return 1;
                case '*':
                case '/': return 2;
                default: return 0;
            }
        }        // Convert to Suffix Format
        public static List<String> ConvertToRearFormat(String str)   
        {
            str = str.Replace(" ", "");
            List<String> list = new List<String>();            Int32 start = 0;
            for (Int32 i = 0; i < str.Length; i++)
            {
                if (!Char.IsDigit(str[i]))
                {
                    if (!(i - 1 < 0 || i == start))
                    {
                        list.Add(str.Substring(start, i - start));
                    }
                    list.Add(str[i].ToString());
                    start = i + 1;
                    continue;
                }
                if (Char.IsDigit(str[i]) && i == str.Length - 1)
                {
                    list.Add(str.Substring(start));
                }
            }
            Stack<Char> stack = new Stack<Char>();
            List<String> res = new List<String>();
            foreach (String s in list)
            {
                if (IsNumber(s))
                {
                    res.Add(s);
                }
                else if (s == "(")
                {
                    stack.Push(s[0]);
                }
                else if (s == ")")
                {
                    while (stack.Count != 0)
                    {
                        if (stack.Peek() == '(')
                        {
                            stack.Pop();
                            break;
                        }
                        res.Add(stack.Pop().ToString());
                    }
                }
                else
                {
                    while(stack.Count != 0 && stack.Peek() != '(' && GetPriority(stack.Peek()) > GetPriority(Convert.ToChar(s)))
                    {
                        res.Add(stack.Pop().ToString());
                    }                    stack.Push(s[0]);
                }
            }
            while (stack.Count != 0)
            {
                res.Add(stack.Pop().ToString());
            }
            return res;
        }        //Get the value of a expression which is expressed in suffix format
        public static Int32 GetValue(List<String> list)   
        {
            Stack<String> temp = new Stack<String>();
            foreach (String s in list)
            {
                temp.Push(s);
                if (!IsNumber(s))
                {
                    temp.Pop();
                    String p1 = temp.Pop();
                    String p2 = temp.Pop();                    temp.Push(Calculate(p1, s[0], p2).ToString());
                }
            }
            return Convert.ToInt32(temp.Pop());
        }        //Calculate the value of p1 op p2.
        public static Int32 Calculate(String s1, Char op, String s2)   
        {
            Int32 p1 = Convert.ToInt32(s1);
            Int32 p2 = Convert.ToInt32(s2);
            switch (op)
            {
                case '+': return p1 + p2;
                case '-': return p1 - p2;
                case '*': return p1 * p2;
                case '/': return p1 / p2;
                default: return 0;
            }
        }        public static void ValueofExpression(String str)
        {
            str = str.Trim().Replace(" ", "");
            if (str.IndexOf(@"/0") > -1)
            {
                Console.WriteLine("the divisor cannot be zero");
                return;
            }
            Char[] cs = str.ToCharArray();
            Int32 openN = (from c in cs where c == '(' select c).Count<Char>();
            Int32 closeN = (from c in cs where c == ')' select c).Count<Char>();
            if (openN != closeN)
            {
                Console.WriteLine("Format is wrong!(because parentheses)");
                return;
            }            List<String> list = new List<String>();
            list = ConvertToRearFormat(str);
            Int32 numofParas = list.FindAll((string s) => { if (IsNumber(s)) return true; else return false; }).Count;
            Int32 numofOps = list.FindAll((String s) => { if (s[0] == '+' || s[0] == '-' || s[0] == '*' || s[0] == '/') return true; else return false; }).Count;
            if (numofParas == numofOps + 1)
            {
                Console.WriteLine(GetValue(list)); 
            }
            else
            {
                Console.WriteLine("Error");
            }
        }        static void Main(string[] args)
        {            
            ValueofExpression("1 + (2 * 3 +5 / 0)");  //the divisor cannot be zero
            ValueofExpression("1 + (2 * 3 + 5 )");    //12
            ValueofExpression("(2 * 2 + 4) * 2");     //16
            ValueofExpression("(2 * 2 + 4 * 2");      //Format is wrong!(because parentheses)
        }
    }
}