当前位置:首页 > 数据结构与算法 > 正文内容

中缀表达式转后缀表达式

admin3个月前 (05-04)数据结构与算法114

转换过程如下:

  1. 1、运算数:直接输出;

  2. 2、左括号:压入堆栈;

  3. 3、右括号:将栈顶的运算符弹出并输出,直到遇到左括号(出栈,不输出);

  4. 4、运算符:若优先级大于栈顶运算符时,则把它压栈;若优先级小于等于栈顶运算符时,将栈顶运算符弹出并输出;再比较新的栈顶运算符,直到该运算符大于栈顶运算符优先级为止,然后将该运算符压栈;

  5. 5、若各对象处理完毕,则把堆栈中存留的运算符一并输出

  6. (以上来自中国大学慕课浙江大学数据结构)

后缀表达式求值看下篇:https://lovedm.club/?id=130

C#代码实现如下:

using System;
using System.Collections.Generic;

namespace 中缀表达式转后缀表达式
{
    class Program
    {
        static void Main(string[] args)
        {
            //string[] expression = { "(", "4", "+", "(", "13", "/", "5", ")", ")" };
            string[] expression = { "(", "(", "10", "*", "(", "6", "/", "(", "(", "9", "+", "3", ")", "*", "-11", ")", ")", ")", "+", "17", ")", "+", "5" };
            foreach (var item in ConvertExpression(expression))
            {
                Console.Write(item + " ");
            }

        }

        /// <summary>
        /// 优先级比较
        /// 只比较“+”,“-”,“*”,“/”和“(”之间的优先级
        /// 且优先级相同时返回false
        /// </summary>
        /// <param name="left">左边的运算符</param>
        /// <param name="right">右边的运算符</param>
        /// <returns>左边的优先级大于右边返回true,小于或等于时返回false</returns>
        public static bool Priority(string left, string right)
        {
            if (left == "+" || left == "-")
            {
                if (right == "*" || right == "/" || right == "+" || right == "-")
                {
                    return false;
                }
            }
            if (left == "*" || left == "/")
            {
                if (right == "*" || right == "/")
                {
                    return false;
                }
            }
            return true;
        }

        /// <summary>
        /// 中缀表达式转后缀表达式
        /// </summary>
        /// <param name="s">以字符串数组形式输入的中缀表达式</param>
        /// <returns>返回后缀表达式的集合</returns>
        public static List<string> ConvertExpression(string[] s)
        {
            int length = s.Length;
            Stack<string> stack = new Stack<string>();
            List<string> answer = new List<string>();
            //遍历所有元素
            for (int i = 0; i < length; i++)
            {
                //遇到运算数直接添加到结果
                int num;
                if (int.TryParse(s[i].ToString(), out num))
                {
                    answer.Add(s[i]);
                }
                //遇到左括号直接压入栈
                if (s[i] == "(")
                {
                    stack.Push("(");
                }
                //遇到右括号依次弹出栈顶元素到结果直至遇到左括号
                if (s[i] == ")")
                {
                    string element = stack.Pop();
                    while (element != "(")
                    {
                        answer.Add(element);
                        element = stack.Pop();
                    }
                }
                //如果是运算符则比较运算符的优先级:
                //1、若优先级大于栈顶运算符则压入栈
                //2、若优先级小于等于栈顶的运算符,则将栈顶运算符弹出并添加到结果,
                //再比较栈顶的新运算符,直至该运算符大于栈顶运算符优先级为止,
                //然后将该运算符压栈
                if (s[i] == "+" || s[i] == "-" || s[i] == "*" || s[i] == "/")
                {
                    //栈内元素为0的话,入栈即可
                    if (stack.Count == 0)
                    {
                        stack.Push(s[i]);
                    }
                    else //否则按照上面的算法
                    {
                        string temp = stack.Peek();
                        if (Priority(s[i], temp))
                        {
                            stack.Push(s[i]);
                        }
                        else
                        {
                            answer.Add(stack.Pop());
                            while (!Priority(s[i], stack.Peek()))
                            {
                                answer.Add(stack.Pop());
                            }
                            stack.Push(s[i]);
                        }
                    }

                }
            }
            //若各对象处理完毕,则把堆栈中存留的运算符一并加入到结果
            while (stack.Count != 0)
            {
                answer.Add(stack.Pop());
            }

            return answer;
        }
    }
}

输出结果如下:

image.png

版权声明:本文由cyhu's essay发布,如需转载请注明出处。

本文链接:https://lovedm.club/?id=129

相关文章

线性表

线性表

线性表(linear list)是数据结构的一种,一个线性表是n个具有相同特性的数据元素的有限序列。数据元素是一个抽象的符号,其具体含义在不同的情况下一般不同。1.集合中必存在唯一的一个“第一元素”。...

单链表

单链表

单链表存储一个直接后继的地址,用一组任意的存储单元存储线性表中的元素。数据域(数据元素)+指针域(指示后继元素存储位置) = 结点,如下图:a和b是两个结点,其中a的指针域保存了指向b的地址。以结点的...

C# 二叉树

C# 二叉树

这里实现了二叉树的创建与插入结点,前中后序遍历的递归实现以及前序遍历的非递归实现,层序遍历的非递归实现。插入结点时采用二叉排序树的方式,没有处理有相同结点时的情况,按下面代码中插入结点时,构成的二叉树...

以层序插入二叉树结点

这里以层序插入二叉树的结点,以先序遍历输出。上一篇关于二叉树的内容在这里:https://lovedm.club/?id=110using System; using Syste...

线性表的顺序结构(顺序表)

线性表的顺序结构(顺序表)

顺序表,线性表的一种,其存储时需要开辟一块足够大的连续的空间,数据之间的存放是相连的,中间没有空隙。顺序表的初始化:需要指定顺序表的大小,这个大小要足够大,还要将元素个数初始化为0。按照位置查找元素:...

二分查找

二分查找

使用二分法对数组进行元素的搜索,返回查找的元素索引,当然使用二分搜索的前提是数组已经完成排序。原始数组有10个元素,要搜索的元素是11。整个排序过程如下:首先原始数组如下:第一次两个指针位置如下:低指...