提要：
1.对上一篇文章的改进：增加括号
2.改变了 字符串转化成中缀表达式的方法
一、依旧是数据结构的知识：
1.将中缀表达式转换成后缀表达式
设算法的输入为中缀表达式infixExp（字符串），输出结果为postfixExp，是保值的后缀表达式。举例：23 + 34 * 45 / (5 + 6 + 7) 转后为后缀： 23 34 45 * 5 6 + 7 + / +2.算法：自左至右扫描infixExp，读入每项并分析其对应的语法成分： 1)当输入的是操作数，则直接输出到postfixExp中。 2)当输入的是左括号，则把它压栈。 3)当输入的是右括号，先判断栈是否为空，若为空则括号不匹配；若非空，则把栈中的项依次弹出，直到遇到第1个左括号为止，将弹出的项输出到postfixExp中(弹出的左括号不输出到postfixExp中)，若没有遇到左括号，则括号也不匹配。4)当输入的是运算符op（ 四则运算+ - */ 之一）时： a)循环，当(栈非空 and 栈顶不是左括号 and 栈顶运算符的优先级不低于输入运算符的优先级时)，反复操作：将栈顶元素弹出，输出到postfixExp中。b)把输入的运算符op压栈。 5)最后，当中缀表达式infixExp的符号序列全部读入后，在栈中可能还会一些项，它们是原来压入还没有处理的语法成分。对待它们的方法是：把它们依次从栈中弹出，并输出到后缀表达式postfixExp的尾部。2.后缀的求值见上一篇文章
二、将字符串变成中缀表达式，保存到Q1中
在没有想到很好的算法。就是将字符串进行分割，把数值保存到分割后的数组resSplit中，然后对原来的字符串res遍历，寻找运算符。
期待找到更好的算法。
//按钮"="的响应代码
protected void ButtonEqual_Click(object sender, EventArgs e)
{
int si=0;
int s=1;//s=0时：上一个元素是数字。s=1时，上一个是符号
String res = TextBoxResult.Text;
char[] str = TextBoxResult.Text.ToCharArray();
string[] resSplit = res.Split(new char[] { '+', '-', '*', '/','(',')' });
try
{
for (int i = 0; i < str.Length; i++)
{
node tmp = new node();//临时节点
if ((str[i]==46||( str[i] - 48 <= 9 && 0 <= str[i] - 48) )&& s == 1)//新加入的元素是数值
{
tmp.sign = false;
while (true )
{
if (resSplit[si] != "")
{
tmp.num = Convert.ToDouble(resSplit[si]);
break;
}
else si++;
}
Q1.Enqueue(tmp);
Label1.Text = Label1.Text + tmp.num;//测试
s = 0;
si++;}
else if ((str[i]==46||( str[i] - 48 <= 9 && 0 <= str[i] - 48)) && s == 0)//新加入的元素是数字，但前面元素也是
{
continue;
}
else
{
tmp.sign = true;
tmp.symbol = str[i];
if (tmp.symbol == '*' || tmp.symbol == '/') tmp.priority = 2;
else if (tmp.symbol == '+' || tmp.symbol == '-') tmp.priority = 1;
s = 1;
Q1.Enqueue(tmp);
Label1.Text = Label1.Text + tmp.symbol;//测试
}
}
change();
double r = calculate();
if(err==false) Label1.Text = Label1.Text + "=" + r+ "<br />";
else Label1.Text = Label1.Text +"error!<br />";//测试
}
catch (Exception ew)
{
Label1.Text = Label1.Text +"error!<br />";//测试
}
}
三 中缀-后缀
public void change()//2) 将中缀表达式转换成后缀表达式；
{
while (Q1.Count != 0)
{
if (Q1.Peek().sign == false)//是数字，放入队列
{
Q2.Enqueue(Q1.Peek());
}
else
{
if (Q1.Peek().symbol == '(')//当输入的是左括号，则把它压栈。
Sc.Push(Q1.Peek());
else if (Q1.Peek().symbol == ')')//当输入的是右括号，
{
if (Sc.Count() == 0)
{
err = true;
break;
}
else
{
while (Sc.Peek().symbol != '(')
{
Q2.Enqueue(Sc.Peek());
Sc.Pop();
if (Sc.Count() == 0)
{
err = true;
break;
}
}
if (Sc.Count() != 0) Sc.Pop();
}
}else
{
while (Sc.Count()!= 0 && Q1.Peek().symbol != '(' && Q1.Peek().priority <= Sc.Peek().priority)
{
Q2.Enqueue(Sc.Peek());
Sc.Pop();
}
Sc.Push(Q1.Peek());
}}
Q1.Dequeue();
}
while (Sc.Count() != 0)
{
if (Sc.Peek().symbol == '(')
{
err = true;
break;
}
Q2.Enqueue(Sc.Peek());
Sc.Pop();
}
}
四 后缀求解
public double calculate() { Stack<node> stmp = new Stack<node>(); double num1 = 0; double num2 = 0; node tmp = new node(); while (Q2.Count != 0) { if (Q2.Peek().sign == false) { stmp.Push(Q2.Peek()); } else if (Q2.Peek().sign == true) { num2 = stmp.Peek().num; stmp.Pop(); num1 = stmp.Peek().num; stmp.Pop(); if (Q2.Peek().symbol == '+') { tmp.num = num1 + num2; tmp.priority = 1; tmp.sign = false; } else if (Q2.Peek().symbol == '-') { tmp.num = num1 - num2; tmp.priority = 1; tmp.sign = false; } else if (Q2.Peek().symbol == '*') { tmp.num = num1 * num2; tmp.priority = 2; tmp.sign = false; } else if (Q2.Peek().symbol == '/') { tmp.num = num1 / num2; tmp.priority = 2; tmp.sign = false; } stmp.Push(tmp); } Q2.Dequeue(); } if (stmp.Count() != 1) err = true; return stmp.Peek().num; }
五、不足：
1 随便写了点，代码还很不规范
2 出现错误时全部报错error!，未进行细分
3 限制为double型，无法达到高精度
4 不支持负数，如-6 计算时会出错，需写成：（0-6)