• 欢迎浏览“String me = Creater\忠实的资深Linux玩家;”,请文明浏览,理性发言,有侵犯你的权益请邮件我(creater@vip.qq.com).
  • 把任何的失败都当作一次尝试,不要自卑;把所有的成功都想成是一种幸运,不要自傲。
  •    5年前 (2013-05-02)  算法/数据结构 |   2 条评论  19 
    文章评分 0 次,平均分 0.0

    题目描述:求中缀表达式的值。例:( a - b ) * ( c + d )。

    两种思路:
    一、同时开两个栈,一个栈存操作符,另一个存操作数,两个同时开工。
    二、先转化为后缀表达式,然后再计算。

    第二种思想,算法是利用栈实现的:
    一、中缀(infix)表达式转后缀(postfix)表达式:

    1.设置一个运算符栈(初始时可以将栈顶运算符置为“#”);

    2. 按顺序扫描中缀表达式,当输入为操作数时就将其输出到后缀表达式中;

    3. 当输入为运算符时,则比较输入运算符和栈顶运算符的优先级。若输入运算符的优先级高于栈顶运算符的优先级,则将输入运算符入栈;否则,栈顶运算符的优先级高于或等于输入运算符的优先级,弹出栈顶运算符到后缀表达式,然后重新比较输入运算符和更新后的栈顶运算符的优先级;

    4. 当输入运算符为“(”时,直接将其入栈;

    5. 当输入运算符为“)”时,将栈顶运算符出栈至后缀表达式,直到栈顶为“(”,然后将“(”和“)”一同抛弃;

    6. 中缀表达式扫描完毕后,将运算符栈依次出栈到后缀表达式,直到栈空(或栈顶为“#”)时停止。

    二、后缀表达式的计算:

    1. 设置一个用于存放操作数的栈,从左至右依次扫描后缀表达式;

    2. 每读入一个操作数就将其入栈,每读入一个运算符就从操作数中取出两个栈顶元素施以该运算操作,并将运算结果作为新的操作数入栈;

    3. 重复1和2 直到后缀表达式读完。

    4. 最后的栈顶操作数即为该后缀表达式的运算结果。

    相关细节问题:

    1、一般情况下,用字符串表示表达式,所以在由中缀转化为后缀时,要注意空格,如果中缀中本来就有空格,就将其直接输入到后缀中即可,否则要在将数字加入到后缀中之后再加一个空格。因为不这样做的话,在用后缀计算表达示的值时,会出现歧义,如“356-7/4+4*”前面356到底是几个数不好确定。

    2.在计算后缀表达式的会值时,要注意计算的顺序,假设先后弹出的两个数为a和b,运算符为c,则应该做运算 b c a 而不是 a c b,这点很容易出错的,如果 c 是 + 和 * 还好,是 - 和 / 的话,结果就错了。

    // mid-exp to post-exp
    void mid2post(string &mid, string &post)
    {
        map<char, int> pri;
        pri['+'] = pri['-'] = 0;
        pri['*'] = pri['/'] = 1;
        pri['('] = -1;
        int len = mid.length();
        for(int i = 0; i < len; i++)
        {    // if digit add to post
            if(mid[i] >= '0' && mid[i] <= '9')
            {
                post += mid[i];   
            }
            else if(mid[i] == ' ')
            {
                post += ' '; // for calculate , it's necessary
                continue;
            }
            else
            {   // stack empty or priority is higher
                if(opt.empty() || pri[mid[i]] > pri[opt.top()] || mid[i] == '(')
                {
                    opt.push(mid[i]);
                }
                else if(mid[i] == ')')
                {
                    while(!opt.empty() && opt.top() != '(')
                    {
                        post += opt.top();
                        opt.pop();
                    }
                    opt.pop();  // pop out '('
                }
                else
                {   // stack empty and prority is not higher
                    while(!opt.empty()&& pri[mid[i]] <= pri[opt.top()])
                    {
                        post += opt.top();
                        opt.pop();
                    }
                    opt.push(mid[i]);
                }
            }
        }
        while(!opt.empty())
        {
            post += opt.top();
            opt.pop();
        }
    }
    double calc(string &post)
    {
        string::iterator it;
        for(it = post.begin(); it != post.end(); it++)
        {
            if(*it >= '0' && *it <= '9')
            {   
                double temp = 0;
                while(*it >= '0' && *it <= '9')
                {
                    temp = temp * 10 + (*it - 48);
                    it++;
                }
                num.push(temp); // not to miss a char
                it--;
            }
            else if(*it == ' ') continue;
            else
            {
                double a = num.top();   num.pop();
                double b = num.top();   num.pop();
                switch(*it)
                {
                    case '+': num.push(b + a); break;
                    case '-': num.push(b - a); break;
                    case '*': num.push(b * a); break;
                    case '/': num.push(b / a); break;
                }
            }
        }
        double result = num.top();
        num.pop();
        return result;
    }
     

    除特别注明外,本站所有文章均为String me = "Creater\忠实的资深Linux玩家";原创,转载请注明出处来自http://unix8.net/home.php/960.html

    关于

    发表评论

    暂无评论

    切换注册

    登录

    忘记密码 ?

    切换登录

    注册

    扫一扫二维码分享