->概念
中缀表达式 9+(3-1)*3+10/2
转换步骤
9 +
9 + (
9 3 + ( -
9 3 1 + ( - )
9 3 1 - +
9 3 1 - + *
9 3 1 - 3 + * +
9 3 1 - 3 * + +
9 3 1 - 3 * + 10 +
9 3 1 - 3 * + 10 + /
9 3 1 - 3 * + 10 2 +/
9 3 1 - 3 * + 10 2 / +
后缀表达式 9 3 1 - 3 * + 10 2 / +
9 3 1 -
9 2 3
9 2 3 *
9 6 +
15 10 2 /
15 5 +
20
转换规则
从左到右遍历中缀表达式的每个数字和符号,若是数字就输出,即成为
后缀表达式的一部分;若是符号,则判断其与栈顶符号的优先级别,是
右括号或优先级低于栈顶符号(乘除优先加减)则栈顶元素依次出栈并
输出,并将当前符号进栈,一直到最终输出后缀表达式为止
/// <summary>
/// 定义级别
/// </summary>
static my[] mylist = {new my{i=,deouce=")"},
new my{i=,deouce="+"},
new my{i=,deouce="-"},
new my{i=,deouce="*"},
new my{i=,deouce="/"},
new my{i=,deouce="("}
};
static void Main(string[] args)
{
string s = "(1000*1000-10)+89*22";
List<string> ds = HouZui(getStr(ggg(s)));
Console.WriteLine(Reuslt(ds));
Console.Read();
}
/// <summary>
/// 计算结果的
/// </summary>
/// <param name="Tstr">后缀表达式</param>
/// <returns>结果</returns>
private static double Reuslt(List<string> Tstr)
{
Stack<double> stack = new Stack<double>();
foreach (var item in Tstr)
{
if (isNumber(item))
{
stack.Push(double.Parse(item));
}
else
{
double d1 = stack.Pop();
double d2 = stack.Pop();
stack.Push(GetResult(item, d2, d1));
}
}
return stack.Pop();
}
//根据中缀表达式转换成后缀表达式
private static List<string> HouZui(string[] ds)
{
List<string> Ts = new List<string>();
Stack<string> stack = new Stack<string>();
for (int i = ; i < ds.Length; i++)
{
string stemp = ds[i];
if (isNumber(stemp))//是数字就直接添加到字符串集合中
{
Ts.Add(stemp);
}
else//是符号就判断
{
string strtemp = " ";
try
{
strtemp = stack.Peek();
}
catch
{
stack.Push(stemp);
continue;
}
if (strtemp == " ")//表示第一次添加
{
stack.Push(stemp);
}
else//比较数据等级大小
{
if (getIntFromList(stemp) == )//判断当前符号是否为右边的括号
{
try
{
while ((strtemp = stack.Pop()) != "(")
{
Ts.Add(strtemp);
}
continue;
}
catch { continue; } }
//如果当前符号不是右边括号
//前面的是否大于当前的,
while (isLowser(strtemp, stemp) && strtemp != "(")
{
strtemp = stack.Pop();
Ts.Add(strtemp);
try
{
strtemp = stack.Peek();
}
catch
{
break;
} }
stack.Push(stemp);
} }
}
string ss = "dd";
try
{ while (ss != " ")
{
ss = stack.Pop();
Ts.Add(ss);
}
}
catch
{
ss = " ";
}
return Ts;
}
/// <summary>
/// 判断栈中的数据级别是否大于于将要加入栈中的符号
/// </summary>
/// <param name="Previous">前一个符号</param>
/// <param name="next">后一个符号</param>
/// <returns>大于为真,否则为假</returns>
private static bool isLowser(string Previous, string next)
{
if (getIntFromList(Previous) > getIntFromList(next))
{
return true;
}
return false;
}
//得到符号的等级
private static int getIntFromList(string s, int i = )
{ if (i == mylist.Length)
{
return ;
} my stmep = mylist[i];
if (stmep.deouce == s)
{
return stmep.i;
}
return getIntFromList(s, ++i);
}
//判断是否是数字
private static bool isNumber(string c)
{
Regex rg = new Regex("\\d");
return rg.IsMatch(c.ToString());
}
//分解字符串,得到符号和数字
private static string ggg(string s)
{
int i = ;
string temp = "";
string c1 = s[i].ToString();
if (s.Length == )
{
if (!isNumber(c1))
{
return " " + c1;
}
else
return c1.ToString();
}
else
{
if (!isNumber(c1))
{
c1 = " " + c1 + " ";
} }
//相等,就加入集合,并进行下一次查找
temp += c1;
return temp + ggg(s.Substring());
}
//得到最终字符串
private static string[] getStr(string s)
{
List<string> Ts = new List<string>();
Ts.AddRange(s.Split(' '));
for (int i = Ts.Count - ; i > -; i--)
{
if (Ts[i] == "")
{
Ts.RemoveAt(i);
}
}
return Ts.ToArray();
}
private static double GetResult(string s, double d1, double d2)
{
Icc i = null;
switch (s)
{
case "+": i = new Add(); break;
case "-": i = new jian(); break;
case "*": i = new cheng(); break;
case "/": i = new Chu(); break;
}
return i.Count(d1, d2);
}
class my
{
public int i { get; set; }
public string deouce { get; set; }
}
}
interface Icc
{
double Count(double d1, double d2);
}
class Add : Icc
{
public double Count(double d1, double d2)
{
return d1 + d2;
}
}
class jian : Icc
{
public double Count(double d1, double d2)
{
return d1 - d2;
}
}
class cheng : Icc
{
public double Count(double d1, double d2)
{
return d1 * d2;
}
}
class Chu : Icc
{
public double Count(double d1, double d2)
{
return d1 / d2;
}
}