逆波兰式分析程序实验目的与要求

  将非后缀式用来表示的算术表达式转换为用逆波兰式来表示的算术表达式，并计算用逆波兰式来表示的算术表达式的值。

实验内容

• 本次实验相对于前几次来说较为简单。对输入的算数表达式进行分析，主要是：
• 遇到操作符和操作数时的处理方法，以及最后的逆波兰式计算这三部分。

实验步骤

1.分析出完整的运算数或者运算符(参考词法分析)。0代表数字，1代表运算符 Tuple为元组数据类型。

    static Tuple<int,string,string> ReadObject(string inputString) 

2.遇到操作符时的栈操作

    static void InsertOp(string op)

• 若取出的字符是运算符，则将该运算符与S1栈栈顶元素比较，
• 如果该运算符优先级(不包括括号运算符)大于S1栈栈顶运算符优先级，则将该运算符进S1栈
• 否则，将S1栈的栈顶运算符弹出，送入S2栈中，直至S1栈栈顶运算符低于（不包括等于）该运算符优先级，最后将该运算符送入S1栈。
• 若取出的字符是“（”，则直接送入S1栈顶。
• 若取出的字符是“）”，则将距离S1栈栈顶最近的“（”之间的运算符，逐个出栈，依次送入S2栈，此时抛弃“（”。

主要字段：

• static Stack numStack = new Stack();//遇到操作数直接压入 numStack
• static Stack opStack = new Stack();//遇到操作符进行分析选择后，压入opStack
• static Stack rpnStack = new Stack();//用于保存生成的逆波兰式
• static StringBuilder rpnExpression = new StringBuilder();//逆波兰式的字符串形式

实验中遇到的问题：

  没有问题

using System;
using System.Collections;
using System.Text;
using static System.Console;
namespace RPN
{
    class Program
    {
        static Stack numStack = new Stack();
        static Stack opStack = new Stack();
        static Stack rpnStack = new Stack();
        static StringBuilder rpnExpression = new StringBuilder();
        static void Main(string[] args)
        {           
            WriteLine("请输入只能包含：int + - * / () ,并且保证合法的算数表达式");
            while (true)
            {
                string inputString = ReadLine();
                int num = 0;
                while (inputString.Length > 0)
                {
                    Tuple<int, string, string> t = ReadObject(inputString);
                    inputString = t.Item3;
                    if (t.Item1 == 0)
                    {
                        num = int.Parse(t.Item2);
                        numStack.Push(num);
                    }
                    else
                    {
                        string op = t.Item2;
                        InsertOp(op);
                    }
                }
                CreateExpression();
                int result = CalExpression();
                WriteLine($"逆波兰表达式为：{rpnExpression}     运算结果为：{result}");
                opStack.Clear();
                numStack.Clear();
                rpnStack.Clear();
                rpnExpression.Clear();
            }
        }
        /// <summary>
        /// 生成逆波兰式
        /// </summary>
        static void CreateExpression()
        {
            while (opStack.Count > 0)
            {
                numStack.Push(opStack.Pop());
            }            
            while (numStack.Count > 0)
            {
                rpnStack.Push(numStack.Pop());
            }
            foreach (object o in rpnStack)
            {
                rpnExpression.Append(o.ToString());
            }
        }
        /// <summary>
        /// 计算逆波兰式
        /// </summary>
        /// <returns></returns>
        static int CalExpression()
        {
            int sum = 0;
            while (rpnStack.Count > 0)
            {
                string o = rpnStack.Pop().ToString();
                switch (o)
                {
                    case "+":
                        int num1 = int.Parse(numStack.Pop().ToString());
                        int num2 = int.Parse(numStack.Pop().ToString());
                        sum = num2 + num1;
                        numStack.Push(sum);
                        break;
                    case "-":
                        num1 = int.Parse(numStack.Pop().ToString());
                        num2 = int.Parse(numStack.Pop().ToString());
                        sum = num2 - num1;
                        numStack.Push(sum);
                        break;
                    case "*":
                        num1 = int.Parse(numStack.Pop().ToString());
                        num2 = int.Parse(numStack.Pop().ToString());
                        sum = num2 * num1;
                        numStack.Push(sum);
                        break;
                    case "/":
                        num1 = int.Parse(numStack.Pop().ToString());
                        num2 = int.Parse(numStack.Pop().ToString());
                        sum = num2 / num1;
                        numStack.Push(sum);
                        break;
                    default:
                        numStack.Push(o);
                        break;
                }
            }
            return sum;
        }

        /// <summary>
        /// 遇到操作符时的栈操作
        /// </summary>
        /// <param name="op"></param>
        static void InsertOp(string op)
        {
            switch (op)
            {
                case "*":
                case "/":
                    {
                        if (opStack.Count > 0)
                        {
                            while (opStack.Count > 0 && (string)opStack.Peek() == "*" || (string)opStack.Peek() == "/")
                            {
                                numStack.Push(opStack.Pop());
                            }
                            opStack.Push(op);
                        }
                        else
                        {
                            opStack.Push(op);
                        }                      
                    }
                    break;
                case "+":
                case "-":
                    {
                        if (opStack.Count > 0)
                        {
                            while (opStack.Count != 0 && (string)opStack.Peek() != "(" && (string)opStack.Peek() != ")")
                            {
                                numStack.Push(opStack.Pop());
                            }
                            opStack.Push(op);
                        }
                        else
                        {
                            opStack.Push(op);
                        }
                    }
                    break;
                case "(":
                    {
                        opStack.Push(op);
                    }
                    break;
                case ")":
                    {
                        if (opStack.Count > 0)
                        {
                            while (opStack.Count != 0 && (string)opStack.Peek() != "(" )
                            {
                                numStack.Push(opStack.Pop());
                            }
                            opStack.Pop();
                        }
                       
                    }
                    break;
            }  
        }

        /// <summary>
        /// 分析出完整的运算数，或者运算符；0代表数字，1代表运算符
        /// </summary>
        /// <param name="inputString"></param>
        /// <returns></returns>
        static Tuple<int,string,string> ReadObject(string inputString)
        {
            int type = 0;//0代表数字，1代表运算符
            StringBuilder sb = new StringBuilder();
            char[] cs = inputString.ToCharArray();
            int index = 0;
            if (cs[index] >= '0' && '9' >= cs[index])
            {
                while (index < inputString.Length && cs[index] >= '0' && '9' >= cs[index])
                {
                    sb.Append(cs[index]);
                    index++;
                }
            }
            else
            {
                type = 1;
                sb.Append(cs[index]);
                index++;
            }
            inputString = inputString.Substring(index, inputString.Length - index);
            return Tuple.Create<int,string, string>(type, sb.ToString(), inputString);
        }
    }
}