中缀表达式转换为后缀表达式求值

2013年5月2日 由 Creater 留言 »

题目描述:求中缀表达式的值。例:( 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;
}
广告位

发表评论

你必须 登陆 方可发表评论.