2011-10-05 13:25 http://blog.csdn.net/yillc/article/details/6844931

提要：

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遍历，寻找运算符。

期待找到更好的算法。

 <p> //按钮"="的响应代码
    protected void ButtonEqual_Click(object sender, EventArgs e)
    {

        int si=0;
        int s=1;//s=0时：上一个元素是数字。s=1时，上一个是符号
    </p><p>        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++;</p><p>                }
                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 />";//测试
        }
    }
</p>

三 中缀-后缀

<p> 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();
                    }
                }</p><p>                else
                {
                    while (Sc.Count()!= 0 && Q1.Peek().symbol != '(' && Q1.Peek().priority <= Sc.Peek().priority)
                    {
                        Q2.Enqueue(Sc.Peek());
                        Sc.Pop();
                    }
                    Sc.Push(Q1.Peek());
                }</p><p>            }
            Q1.Dequeue();
        }
        while (Sc.Count() != 0)
        {
            if (Sc.Peek().symbol == '(')
            {
                err = true;
                break;
            }
            Q2.Enqueue(Sc.Peek());
            Sc.Pop();
        }</p><p>
    }</p>
四 后缀求解

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)