首页 > 编程语言 > 详细

shunting-yard 调度场算法、中缀表达式转逆波兰表达式

时间:2018-03-22 01:03:37      阅读:403      评论:0      收藏:0      [点我收藏+]

 

中缀表达式

1*(2+3)

这就是一个中缀表达式,运算符在数字之间,计算机处理前缀表达式和后缀表达式比较容易,但处理中缀表达式却不太容易,因此,我们需要使用shunting-yard Algorithm(调度场算法)来将中缀表达式转换为后缀表达式(即逆波兰表达式),然后求解。

上面的中缀表达式转后缀表达式后为:

1 2 3 + *

调度场算法

为了将中缀表达式转为后缀表达式,使用调度场算法,算法思想如下:

  准备两个栈,一个用于存放数字,一个用于存放操作符。

  从左到右遍历表达式,如果是数字,直接入栈。(注意数字可能是多位数甚至小数)

  如果是符号:

    如果栈为空,或者当前符号为‘ ( ’,或者栈顶为‘ ( ‘,直接入栈。

    如果当前运算符优先级高于栈顶运算符的优先级,则入栈。(注意是高于,等于也不行)

    如果当前运算符优先级不高于栈顶运算符,先从存符号的栈中取出一个操作符,从存数据的栈中取出两个数字,将它们做一次运算并将结果压入数据栈,最后再把当前运算符压入符号栈。

    如果当前符号是‘ ) ‘,不断重复上面划线部分的操作,直到取出的操作符是‘ ( ‘为止。

  表达式遍历完后,不断重复上面划线部分的操作,直到符号栈为空,此时数据栈还有一个数字,那就是原表达式的值。

这样就基本完成了。

这里再来讨论一下负号的处理,如何判断 ‘ - ‘ 是减号还是负号呢?

  如果‘ - ‘出现在表达式开头,一定是负号。

  如果‘ - ‘出现在数字后面,一定是减号。

  如果‘ - ‘出现在‘ ( ‘后面,一定是负号。

  如果‘ - ‘出现在‘ ) ‘后面,一定是减号。

综上可以看出,只要‘ - ’在表达式开头或者‘ ( ‘后面就可以判断为负号,但是判断之后怎么处理呢?

有两种办法,一种是在判断为负号的时候将数字0压入数据栈,然后将负号压入符号栈,可以看做是零减去一个数字。

另一种办法是,如果判断为负号,将下一个压入数据栈的数字乘上 -1。采用这种方法需要注意,如果括号内只有一个负数而没有计算式,按照上面的判断法则,下一个‘ ) ‘将直接被压入栈,从而导致奇怪的事情发生,只要在‘ ) ‘入栈前特判一下即可避免这种问题。(下面代码采用第二种方法)

 

C++代码实现如下

 

#include <iostream>
#include <string>
#include <cstring>
#include <stack>
using namespace std;

int op[55];         //确定运算符的优先级

/* string转数字 */
double toDig(string str) {
    double n = 0, mag = 0.1;
    for(int i = 0; i < str.length(); i++) {
        if(str[i]==.) break;
        mag *= 10;
    }
    for(int i = 0; i < str.length(); i++) {
        if(str[i]==.) continue;
        n += mag*(str[i] - 0);
        mag /= 10;
    }
    return n;
}

/* 计算并返回结果 */
double getAns(double a, double b, char c) {
    switch (c) {
        case +: return b+a;
        case -: return b-a;
        case *: return b*a;
        case /: return b/a;
    }
}

/* shunting-yard */
double shunting(string str) {
    stack<double > iStk;
    stack<char> strStk;
    for(int i = 0; i < str.length();) {
        if( (str[i]>=0 && str[i]<=9) || (i==0&&str[i]==-) || (str[i]==-&&str[i-1]==()) {
            // 判断是否为数字或负号
            string s1;
            int f = 1;
            if(str[i]==-) {
                f=-1;
                i++;
            }
            while((str[i]>=0 && str[i]<=9) || str[i]==.) {
                s1 += str[i++];
            }
            iStk.push(f*toDig(s1));
        } else {    //不是数字或负号,则为操作符或括号
            // 如果栈为空、或操作符为‘(‘、或栈顶为‘(‘、或当前操作符的优先级大于栈顶操作符,则操作符入栈
            if(strStk.empty() || str[i]==( || strStk.top()==( || (str[i]!=)&&op[str[i]] > op[strStk.top()])) {
                if(str[i]==) && strStk.top()==() strStk.pop();  //当前符号和栈顶是一对括号则消除它们
                else strStk.push(str[i]);
            }
            else if(str[i] == )) {
                // 如果当前是‘)‘,则做运算直到栈顶是‘(‘
                char c = strStk.top();
                while(c != () {
                    double a = iStk.top();
                    iStk.pop();
                    double b = iStk.top();
                    iStk.pop();
                    strStk.pop();
                    iStk.push(getAns(a,b,c));
                    c = strStk.top();
                }
                strStk.pop();
            }
            else {
                // 否则,说明当前运算符优先级等于或小于栈顶运算符,将栈顶操作符取出做一次运算,将运算结果压栈,最后再将当前操作符入栈
                double a = iStk.top();
                iStk.pop();
                double b = iStk.top();
                iStk.pop();
                char c = strStk.top();
                strStk.pop();
                iStk.push(getAns(a,b,c));
                strStk.push(str[i]);
            }
            i++;
        }
    }
    // 表达式处理完后,不断运算直到操作符空栈,此时数据栈剩下的一个数据就是最终结果
    while(!strStk.empty()) {
        double a = iStk.top();
        iStk.pop();
        double b = iStk.top();
        iStk.pop();
        char c = strStk.top();
        strStk.pop();
        iStk.push(getAns(a,b,c));
    }
    return iStk.top();
}

int main() {
    string s;
    memset(op,1,sizeof(op));
    op[+] = op[-] = 0;
    op[*] = op[/] = 1;
    while(cin >> s) {
        cout << shunting(s) << endl;
    }
    return 0;
}

 

shunting-yard 调度场算法、中缀表达式转逆波兰表达式

原文:https://www.cnblogs.com/magisk/p/8620303.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!