数据结构之——栈在表达式求值中的应用
2009/08/25
传统计算的模式是“一个运算符，两个操作数”，但这样的运算效率很低，如何使用“多运算符，多操作数”进行运算将显得非常必要，而要使用多操作符，首先要解决的问题就是运算符的优先级问题，以及如何实现分步计算。这其中就要用到栈，采用其“只在一端操作”的特性进行设计。
图 1
设计思路：
图 2
namespace 表达式求值
{
class ExpSolving
{
//定义栈stknum用以存储数字
Stack stknum = new Stack();
//定义栈stkop用以存储运算符
Stack stkop = new Stack();
///
/// 初始化栈
///
private void InitiateStack()
{
stknum.Clear();
stkop.Clear();
stkop.Push("=");
}
///
/// 判断栈顶运算符与输入运算符的优先级
///
/// stktop">栈顶字符
/// input">输入字符
///string
private string Precede(string stktop, string input)
{
int Q1 = 0, Q2 = 0;
if (stktop == "+" || stktop == "-" || stktop == "*" || stktop == "/")
{
switch (stktop)
{
case "*":
case "/":
Q1 = 13;
break;
case "+":
case "-":
Q1 = 12;
break;
}
switch (input)
{
case "(":
Q2 = 15;
break;
case "=":
Q2 = 11;
break;
case "*":
case "/":
Q2 = 13;
break;
case "+":
case "-":
Q2 = 12;
break;
case ")":
Q2 = 11;
break;
}
}
else
{
switch (stktop)
{
case ")":
Q1 = 15;
break;
case "(":
Q1 = 11;
break;
case "=":
Q1 = 11;
break;
}
switch (input)
{
case ")":
Q2 = 15;
break;
case "(":
Q2 = 11;
break;
case "=":
Q2 = 11;
break;
case "*":
case "/":
Q2 = 13;
break;
case "+":
case "-":
Q2 = 12;
break;
}
}
if ((stktop == "(" && input == ")") || (stktop == "=" && input == "="))
return "=";
if (stktop == ")" && input == "(")
{
return "#";
}
else if (stktop == "(" && input == "=")
{
return "#";
}
else if (stktop == "=" && input == ")")
{
return "#";
}
if (Q1 == Q2)
{
if ((stktop == "(" && input == "(") || (stktop == "=" && input == "("))
return "<";
else
return ">";
}
else if (Q1 > Q2)
return ">";
else
return "<";
}
///
/// 判断输入字符是否为运算符
///
/// inputstr">输入字符
///如果输入的是运算符，则返回1；如果是数字则返回0；异常返回-1
private int IsOp(string inputstr)
{
switch (inputstr)
{
case "+":
case "-":
case "*":
case "/":
case "(":
case ")":
case "=":
//是运算符返回1
return 1;
case ".":
return 0;
default:
//如果是数字
if (double.IsNaN(Convert.ToDouble(inputstr)) == false)
return 0;
//如果既不是运算符又不是数字
else
//异常返回-1
return -1;
}
}
///
/// 执行计算操作
///
/// a">操作数1
/// op">运算符
/// b">操作数2
///double
private double Operate(double a, string op, double b)
{
switch (op)
{
case "+":
return (a + b);
case "-":
return (a - b);
case "*":
return (a * b);
case "/":
return (a / b);
case "Mod":
return (a % b);
case "x^y":
return (Math.Pow(a, b));
case "y√x":
return (Math.Pow(a, (Math.Pow(b, -1))));
default:
return 0;
}
}
///
/// 计算表达式
///
/// expstr">表达式
public double CalcExp(string expstr)
{
InitiateStack();
if (expstr != "")
{
//将表达式中的空格去除
expstr = expstr.Replace(" ", "");
expstr += "=";
//计算字符的长度
int len = expstr.Length;
//索引
int index = 0, is_op = 0;
double a = 0.0, b = 0.0;
string op = "", numstr = "";
string c = expstr.Substring(index, 1);
while (c != "=" || stkop.Peek().ToString() != "=")
{
is_op = IsOp(c);
//如果是数字
if (is_op == 0)
{
//连上已有的数字字符
numstr += c;
//读取下一个字符
if (index < len)
{
index++;
c = expstr.Substring(index, 1);
}
}
//如果是运算符
else if (is_op == 1)
{
//判断优先级，并根据优先级进行相应操作
switch (Precede(stkop.Peek().ToString(), c))
{
//如果栈顶运算符的优先级小于输入的运算符
case "<":
//将数字字符串中的数字压入栈stknum中
if (numstr != "")
stknum.Push(Convert.ToDouble(numstr));
//将运算符压入栈stkop中
stkop.Push(c);
//获取下一个字符
if (index < len)
{
index++;
c = expstr.Substring(index, 1);
}
//初始化数字字符串
numstr = "";
break;
//如果栈顶运算符的优先级等于输入的运算符
case "=":
//脱括号（左括号）
stkop.Pop();
//获取下一个字符
if (index < len)
{
index++;
c = expstr.Substring(index, 1);
}
break;
//如果栈顶运算符的优先级大于输入的运算符
case ">":
//将数字字符串中的数字压入栈stknum中
if (numstr != "")
stknum.Push(Convert.ToDouble(numstr));
//获取操作数
b = Convert.ToDouble(stknum.Pop());
a = Convert.ToDouble(stknum.Pop());
//获取运算符
op = stkop.Pop().ToString();
//执行分布计算
stknum.Push(Convert.ToDouble(Operate(a, op, b)));
//初始化数字字符串
numstr = "";
break;
}
}
else
{
return 0;
}
}
}
else
{
return 0;
}
return Convert.ToDouble(stknum.Peek());
}
static void Main(string[] args)
{
ExpSolving es = new ExpSolving();
while (true)
{
Console.Write("请输入表达式：");
string exp = Console.ReadLine();
Console.Write("\t" + exp + " = " + es.CalcExp(exp) + "\n");
}
}
}
}