中缀表达式转后缀表达式
转换过程如下:
1、运算数:直接输出;
2、左括号:压入堆栈;
3、右括号:将栈顶的运算符弹出并输出,直到遇到左括号(出栈,不输出);
4、运算符:若优先级大于栈顶运算符时,则把它压栈;若优先级小于等于栈顶运算符时,将栈顶运算符弹出并输出;再比较新的栈顶运算符,直到该运算符大于栈顶运算符优先级为止,然后将该运算符压栈;
5、若各对象处理完毕,则把堆栈中存留的运算符一并输出
(以上来自中国大学慕课浙江大学数据结构)
后缀表达式求值看下篇: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;
}
}
}输出结果如下:




鲁公网安备 37148202000241号