前缀表示法

前缀表示法又叫波兰表示法，他的操作符置于操作数的前面（例：+ 1 2），是波兰数学家扬·武卡谢维奇1920年代引入的，用于简化命题逻辑。因为我们一般认为操作符是在操作数中间的，所以在日常生活中用的不多，但在计算机科学领域占有一席之地。一般的表示法对计算机来说处理很麻烦，每个符号都要考虑优先级，还有括号这种会打乱优先级的存在，将使计算机花费大量的资源进行解析。而前缀表示法没有优先级的概念，他是按顺序处理的。 
举个例子：9-2*3这个式子，计算机需要先分析优先级，先乘后减，找到2*3，再进行减操作；化成前缀表示法就是：- 9 * 2 3，计算机可以依次读取，操作符作用于后一个操作数，遇到减就是让9减去后面的数，而跟着9的是乘，也就是说让9减去乘的结果，这对计算机来说很简单，按顺序来就行了。 
这是一个前缀表达式的计算过程，可以看出每次只需计算第一个满足操作符后跟两个操作数的式子，直到最后就是结果了。

中缀表示法. 
这也就是我们一般的表示法，他的操作符置于操作数的中间（例：1 + 2），前面也说过这种方法不容易被计算机解析，但他符合人们的普遍用法，许多编程语言也就用这种方法了。在中缀表示法中括号是必须有的，要不然运算顺序会乱掉。

后缀表示法 
后缀表示法又叫逆波兰表示法，他的操作符置于操作数的后面（例：1 2 +），他和前缀表示法都对计算机比较友好，但他很容易用堆栈解析，所以在计算机中用的很多。他的解释过程一般是：操作数入栈；遇到操作符时，操作数出栈，求值，将结果入栈；当一遍后，栈顶就是表达式的值。因此逆波兰表达式的求值使用堆栈结构很容易实现，和能很快求值。 
注意：逆波兰记法并不是简单的波兰表达式的反转。因为对于不满足交换律的操作符，它的操作数写法仍然是常规顺序，如，波兰记法“/ 6 3”的逆波兰记法是“6 3 /”而不是“3 6 /”；数字的数位写法也是常规顺序。 
为了更好的了解前缀表达式的计算过程，举个例子：5 1 2 + 4 * + 3 -，计算过程如下 
复制代码代码如下:

表示法间转化 
人工转换方式：使用计算机转换方式 
这里介绍一种简单的中缀表达式转化前后缀表达式的方法，比如这个式子：a+b*c-(d+e)。 
按照运算符的优先级对所有的运算单位加括号

• 式子变成：((a+(b*c))-(d+e))。 
  

• 变成前缀表达式，把运算符号移动到对应的括号前面 
  式子变成：-( +(a *(bc)) +(de)) 
  去掉括号：-+a*bc+de

• 变成后缀表达式，把运算符号移动到对应的括号后面 
  式子变成：((a(bc)* )+ (de)+ )- 
  去掉括号：abc*+de+-

使用栈的属性写出的简化小例，，，此例可转换没有括号的中缀表达式到后缀表达式，， 
查看带有括号的完整转换：代码实现以描述

using System;

using System.Collections;

using System.Collections.Generic;

namespace 写着玩的练习

{

    class Program

    {

        static void Main(string[] args)

        {

            //运行时用建议输入空格

            Console.WriteLine("请输入您要转换的表达式：");

            string inputstr = Console.ReadLine();

            //测试用

            // string inputstr = "9 * 3 + 10 / 2"; 

            Console.WriteLine("您转换后的结果为：");

            change(inputstr);

            Console.ReadKey();

        }

        private static void change(string inputstr)

        {

            //用于存符号的栈

            Stack<char> stackChar = new Stack<char>();

            //将输入转为字符数组

            char[] arrChar = inputstr.ToCharArray();

            for (int i = 0; i < arrChar.Length; i++)

            {

                //数字空格直接输出

                if (arrChar[i] <= '9' && arrChar[i] >= '0')

                {

                    Console.Write(arrChar[i]);

                }

                if (arrChar[i] == ' ')

                {

                    Console.Write(" ");

                }

                 //如果是符号

                switch (arrChar[i])

                {

                    case '+':

                    case '-':

                        if(stackChar.Count == 0)  //栈为空直接添加

                        {

                            stackChar.Push(arrChar[i]);

                        }

                        else  //不为空判断在添加

                        {

                            //若此时栈顶是乘除，打印输出

                            if((stackChar.Peek() == '*') || (stackChar.Peek() == '/'))

                            {

                                //取出栈中所有符号，打印，，并清空栈

                                for (int j = 0; j < stackChar.Count; j++)

                                {

                                    Console.Write(stackChar.Pop());

                                }                               

                                stackChar.Push(arrChar[i]);

                            }

                            //若栈顶是+ - ，，进栈

                            if ((stackChar.Peek() == '-') || (stackChar.Peek() == '+'))

                            {

                                stackChar.Push(arrChar[i]);                             

                            }

                        }

                        break;

                    case '*':

                    case '/':

                        if (stackChar.Count == 0)

                        {

                            stackChar.Push(arrChar[i]);                           

                        }

                        else

                        {

                            //若此时栈顶是乘除，进栈

                            if ((stackChar.Peek() == '*') || (stackChar.Peek() == '/'))

                            {                                

                                stackChar.Push(arrChar[i]);

                            }

                            //若栈顶是+ -  进栈，，

                            if ((stackChar.Peek() == '-') || (stackChar.Peek() == '+'))

                            {                               

                                stackChar.Push(arrChar[i]);                               

                            }

                        }

                        break;

                }

            }

           //遍历栈中所有剩余符号

            for (int i = 0; i < stackChar.Count; i++)

            {

                Console.Write(stackChar.Pop());

            }

        }

    }

}

运行图： 

作者：Czhenya

链接：https://czhenya.blog.csdn.net/article/details/78066521

来源：CSDN
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。