【数据结构】【C#】011-栈的应用：📟表达式求值
2018-10-13 本文已影响67人
lijianfex
C#数据结构：栈的应用：表达式求值
后缀表达式
在我们日常生活中所见表达式都是中缀表达式，如 “5*(3+7)-4/2”,这中表达式符合我们的思维逻辑，可读性强，但是不利于计算机的解析。由波兰逻辑学家J.Lukasiewicz发明出后缀表达式，比如上式转变为后缀表达式”5 3 7 + * 4 2 / -“,这种人类难以适应的表达顺序，计算机却很受用。
中缀表达式转后缀表达式
如：中缀表达式”5*(3+7)-4/2”转为”5 3 7 + * 4 2 / -“
规则：顺序遍历数字和符号，数字输出，成为后缀表达式的一部分，遇符号则判断栈顶元素与其的优先级，若为右括号或者优先级不高于栈顶元素，则将栈顶元素依次出栈并输出，并将当前符号进栈，直到后缀表达式输出完成。
①5输出，’’入栈，’(‘入栈，3输出，’+’入栈，7输出。
输出：5 3 7
②遇到’)’，则将’(‘之前的符号全部出栈输出。
输出：5 3 7 +
③遇到’-‘，优先级比栈顶’ ‘低，’* ‘出栈输出，’-‘进栈。
输出：5 3 7 + *
④输出4，遇到’/’比栈顶’-‘高，’/’进栈，输出2，表达式读取结束，栈内符号依次输出。
输出：5 3 7 + * 4 2 / -
中缀表达式转后缀表达式结束
计算机应用后缀表达式的过程：
如后缀表达式：”5 3 7 + * 4 2 / -”
规则：从左到右遍历表达式的每一个数字和符号，遇到数字就进栈，遇到是符号，就将处于栈顶的两个数字出栈，进行运算，运算结果进栈，一直到最终获得结果。
①初始化一个空栈。此栈用来对要运算的数字进出使用。
②后缀表达式中前三个都是数字，所以5,3,7进栈。
③接下来是’+’运算符，将栈顶的两个元素出栈进行加法运算，再将结果进栈。
④之后是’*’运算符，将栈顶的两个元素出栈进行运算，将运算结果再进栈。
⑤之后4,2进栈，遇’/’将2,4出栈，2作为除数，4作为被除数。
⑥之后遇’-‘，50作为被减数。48入栈，最后出栈，栈为空结果为48.
using System;
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
/// <summary>
/// 栈的应用
/// </summary>
public class StackAppliction
{
#region 1、括号匹配问题 :（{[]}）
/// <summary>
/// 括号匹配算法（栈的应用）
/// </summary>
/// <param name="str"></param>
/// <returns></returns>
public bool BracketMatch(string str)
{
if (str == string.Empty || str == null)//校验字符括号是否为空
{
Debug.Log("字符括号为空！括号匹配失败！");
return false;
}
LinkStack<char> stack = new LinkStack<char>(); //用来存储左括号(此处使用了之前自己定义的链栈结构)
//Stack<char> stack = new Stack<char>();//系统提供的栈
for (int i = 0; i < str.Length; i++)//读取括号字符串
{
switch (str[i])
{
case '(':
case '[':
case '{':
stack.Push(str[i]);//左括号进栈
break;
case ')':
case ']':
case '}':
if (stack.IsEmpty())//使用系统提供的栈：stack.Count==0
{
Debug.Log("右括号 " + str[i] + " 多余！括号匹配失败！");
return false;
}
else
{
char left = stack.Peek();//访问左括号栈顶值
if (Match(left, str[i])) //判断左右括号类型
{
stack.Pop(); //匹配成功,出栈顶值
}
else
{
Debug.Log("左括号: " + left + " 与右括号： " + str[i] + " 不同类型！括号匹配失败！ ");
return false;
}
}
break;
default:
break;
}
}
if (stack.IsEmpty())//使用系统提供的栈：stack.Count==0
{
Debug.Log("括号匹配成功！");
return true;
}
Debug.Log("左括号: " + stack.Peek() + " 多余！括号匹配失败！");
return false;
}
/// <summary>
/// 判断左括号与右括号是否同类型
/// </summary>
/// <param name="l">左括号</param>
/// <param name="r">右括号</param>
/// <returns></returns>
private bool Match(char l, char r)
{
if ((l == '(') && (r == ')'))
{
return true;
}
if ((l == '[') && (r == ']'))
{
return true;
}
if ((l == '{') && (r == '}'))
{
return true;
}
return false;
}
#endregion
由于需要检查表达式的括号是否匹配,上方的代码块被引入；
下方是具体的表达式求值过程：
#region 2、表达式求值: "5 * ( ( 3 + 7 )+(3*2)^2 ) - 4 / 2"
//2、表达式求值：
public int ExpEvaluation(string middleExp)
{
//1、将str 中缀表达式转为后缀表达式
string TrailExp = ToTrailExp(middleExp);
//2、对后缀表达式进行求值操作
return TrailExpEvalution(TrailExp);
}
/// <summary>
/// 中缀表达式转为后缀表达式
/// </summary>
/// <param name="str">中缀表达式</param>
/// <returns>后缀表达式</returns>
public string ToTrailExp(string str)
{
string traiExp = null;
if (str == null || str == string.Empty)//校验str是否空
{
return null;
}
if (!BracketMatch(str))//判断是否平衡圆括号
{
Debug.Log("表达式的圆括号不平衡，表达式有误！");
return null;
}
Stack<char> optrStack = new Stack<char>(); //操作符栈
for (int i = 0; i < str.Length; i++)
{
switch (str[i])
{
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
traiExp += str[i];
break;
case ' ':
break;
case '+':
case '-':
case '*':
case '/':
case '^':
if (optrStack.Count == 0)
{
optrStack.Push(str[i]);
}
else
{
char op = optrStack.Peek();
if (op == '(')
{
optrStack.Push(str[i]);
}
else
{
if (Priority(str[i]) <= Priority(op))
{
traiExp += optrStack.Pop();
optrStack.Push(str[i]);
}
else
{
optrStack.Push(str[i]);
}
}
}
break;
case '('://碰到左括号，直接入栈
optrStack.Push(str[i]);
break;
case ')': //一直出栈至首次出栈的"("
while (optrStack.Count > 0 && optrStack.Peek() != '(')
{
traiExp += optrStack.Pop();
}
if (optrStack.Count != 0)
{
optrStack.Pop();
}
break;
default:
break;
}
}
while (optrStack.Count != 0) //把剩余操作符出栈并输出
{
traiExp += optrStack.Pop();
}
return traiExp;
}
/// <summary>
/// 判断操作符的优先级
/// </summary>
/// <param name="c"></param>
/// <returns></returns>
private int Priority(char c)
{
switch (c)
{
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
default:
return -1;
}
}
/// <summary>
/// 对后缀表达式进行求值操作
/// </summary>
/// <param name="trailExp">后缀表达式</param>
/// <returns>结果</returns>
public int TrailExpEvalution(string trailExp)
{
if (trailExp == null || trailExp == string.Empty) //校验是否空
{
return -1;
}
Stack<int> numStack = new Stack<int>();
for (int i = 0; i < trailExp.Length; i++)
{
int n1, n2;
switch (trailExp[i])
{
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
numStack.Push(int.Parse(trailExp[i].ToString()));
break;
case ' ':
break;
case '+':
n1 = numStack.Pop();
n2 = numStack.Pop();
numStack.Push(n1 + n2);
break;
case '-':
n1 = numStack.Pop();//减数
n2 = numStack.Pop();//被减数
numStack.Push(n2 - n1);
break;
case '*':
n1 = numStack.Pop();
n2 = numStack.Pop();
numStack.Push(n2 * n1);
break;
case '/':
n1 = numStack.Pop();//除数
n2 = numStack.Pop();//被除数
numStack.Push(n2 / n1);
break;
case '^':
n1 = numStack.Pop();//幂数
n2 = numStack.Pop();//低数
numStack.Push((int)Math.Pow(n2, n1));
break;
default:
break;
}
}
return numStack.Pop();
}
#endregion
}
表达式求值算法测试：
using System;
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class _010_StackAppliction : MonoBehaviour
{
void Start()
{
StackAppliction appliction = new StackAppliction();
string str = "5 * ( ( 3 + 7 )+(3*2)^2 ) - 4 / 2";
print("中缀表达式： " + str);
print("后缀表达式： " + appliction.ToTrailExp(str));
print("表达式结果： " + appliction.ExpEvaluation(str));
}
}
输出结果：
img.jpg
注：
1、主要利用栈的先进后出特性，可以算是一个简单的计算器
2、该例子只适用于运算数为0-9的个位数，两位数需要另写算法，将两个相邻数字处理为一个整体。（可以思考下处理方式！）
