跳至正文
View Categories

2 min read

主要内容 #

  1. 问题分析
  2. 举例说明
  3. 参考代码

1. 问题分析 #

根据上节课的讲解，我们学会如何求画解后缀表达式的值。但是对于普通用户来说，让其输入一个正确的后缀表达式显然是不现实的，我们只能要求他们输入一个正确的普通表达式。这就引出了一个问题，如何将一个普通表达式转换为后缀表达式？
幸运的是，针对这个问题伟人迪杰斯特拉给出了一个完美的解决方案，称为调用场算法，该算法可以实现将一个普通表达式转换为后缀表达式。
调用场算法的实现，需要借助一个空栈（假设栈名为Optr）和一个空数组（假设名为postexp）。对于给定的一个普通表达式，调用场算法的转换过程为：逐个遍历表达式中的每个字符：

  • 如果为‘0’～‘9’的字符，将其添加到postexp数组的末尾。
  • 如果该字符为除'(‘和’)’以外的运算符，将其与Optr栈顶的运算符进行大小比较，如果该运算符大于栈顶运算符，则将其入栈；反之，如果该运算符小于栈顶运算符，则将栈顶运算符出栈并添加到postexp数组的尾部，然后继续拿当前的运算符座大小比较，以此类推。
  • 如果该字符为'(‘运算符，直接入栈；如果为’)’运算符，依次取出Optr栈顶运算符并将其添加到postexp数组末尾，知道遇到'(‘字符为止（注意'(‘字符也从栈顶取出，但不将其添加到postexp数组中）。

依照以上处理过程，直到将普通表达式遍历完毕，如果Optr栈中仍有运算符，依次将他们出栈并添加到postexp数组尾部。最终，postexp数组内存储的就是转换后的后缀表达式。
值得一提的是，第2步中关于运算符的大小比较，迪杰斯特拉给出了如下的表格：

如表中所示，假设栈顶运算符为*，当前遍历到的运算符为+，则根据表中第3行第1列可知，*>+，即当前运算符小于栈顶运算符。根据调用场算法的处理规则，需要将*出栈并添加到postexp数组的尾部，继续用+运算符同新的栈顶运算符做比较，由此类推。

2. 举例说明 #

以3!+4*2/(1-5)^2为例，接下来为大家演示用场算法的整个转换过程。遍历整个表达式：
1）对于字符3，直接将其添加到postexp数组尾部：

2）遍历至！，将其与Optr栈顶字符进行比较，由于此时Optr为空栈，因此直接将！入栈：

3）遍历至+，Optr栈顶运算符!>+，将!从Optr栈中取出变添加到postexp数组末尾。此时，Optr栈为空，将+入栈：

4）遍历至4，直接添加到postexp数组末尾：

5）遍历至*，OPtr栈顶运算符+<*所以直接将*入栈：

6）遍历至2，将其添加到postexp数组的末尾：

7）遍历至/，Optr栈顶运算符*>/,将*取出添加到postexp数组末尾：

继续用/同Optr栈顶的+运算符比较，+</，将/入栈：

8）遍历至（，直接入栈：

9）遍历至1，将其添加到postexp数组末尾：

10）遍历至-，Optr栈顶运算符（<-，将-入栈：

11）遍历至5，添加到postexp数组末尾：

12）遍历至)，对Optr栈一直作出栈操作并将出栈元素添加到postexp数组末尾，知道将(取出：

13)遍历至^，Optr栈顶运算符/<^，将^入栈：

14）遍历至2，将其添加到postexp数组末尾：

15）将Optr栈做出栈操作，并逐个将出栈元素添加到postexp数组末尾，直至Optr栈为空：

显然，postexp数组中存储的就是3!+4*2/(1-5)^2对应的后缀表达式。

3. 参考程序 #

//中缀表达式转后缀(只支持+，-，*，/四种运算)
#include<iostream>
#include<string>
#include<stack>

using namespace std;

int prio(char op)                   //给运算符优先级排序
{
    int priority;
    if (op == '*' || op == '/')
        priority = 2;
    if (op == '+' || op == '-')
        priority = 1;
    if (op == '(')
        priority = 0;
    return priority;
}
bool Trans(string &str,string &str1)     //引用传递
{
    stack<char> s;                   //定义一个char类型的栈s
    int i;
    for (i = 0; i<str.size(); i++)
    {
        if (str[i] >= '0' && str[i] <= '9'||str[i] >= 'a' && str[i] <= 'z')      //如果是数字，直接入栈
        {
            str1+=str[i];
        }
        else                          //否则不是数字
        {
            if (s.empty())            //栈空则入站
                s.push(str[i]);
            else if (str[i] == '(')   //左括号入栈
                s.push(str[i]);
            else if (str[i] == ')')    //如果是右括号，只要栈顶不是左括号，就弹出并输出
            {
                while (s.top() != '(')
                {
                    str1+= s.top();
                    s.pop();
                }
                s.pop();                 //弹出左括号，但不输出
            }
            else
            {
                while (prio(str[i]) <= prio(s.top()))   //栈顶优先级大于等于当前运算符，则输出
                {
                    str1+= s.top();
                    s.pop();
                    if (s.empty())      //栈为空，停止
                        break;
                }
                s.push(str[i]);   //把当前运算符入栈
            }
        }
    }
    while (!s.empty())        //最后，如果栈不空，则弹出所有元素并输出
    {
        str1+= s.top();
        s.pop();
    }
    return true;
}
int main()                  //主程序
{
    string infix;
    string postfix;
    cout << "请输入中缀表达式：" << infix << endl;
    cin >> infix;
    Trans(infix,postfix);
    cout << "后缀表达式为：" << postfix << endl;
    return 1;
}

例如输入：a+b*c+(d*e+f)*g
后缀表达式为：abc*+de*f+g*+

What are your Feelings