Infix到后缀转换

Question

我编写了一个C++程序，使用递归将infix表达式转换为后缀表达式。我想知道是否可以在可能的情况下加以改进。我们可以通过不使用堆栈来改进它吗？我在这里使用一个vector<char>作为堆栈。

#include <iostream>
#include <vector>
std::string inp;
int i, len;


std::vector<char> ops;
void convert()
{
    char ch = inp[i];
    if (i > len)
        return;
    else if (ch == '(')
    {
        i++;
        convert();
    }
    else if (ch == ')')
    {
        std::cout << ops[ops.size()-1];
        ops.pop_back();
        i++;
        convert();
    }
    else if (isdigit(ch))
    {
        i++;
        std::cout << ch;
        convert();
    }
    else if ((ch == '+') || (ch == '*'))
    {
        i++;
        ops.push_back(ch);
        convert();
    }
}


int main()
{
    std::cout << "Infix to postfix conversion using recursion" << std::endl;
    i = 0;
    inp = "(5+5)";
    len = inp.length();
    convert();
    std::cout << "\n";
    ops.clear(); i = 0;
    inp = "((5+5)*(6+6))";
    len = inp.length();
    convert();
    std::cout << "\n";
    ops.clear(); i = 0;
    inp = "((4+8)*((5+5)*(6+6)))";
    len = inp.length();
    convert();
    std::cout << "\n";
    return 0;
}

Answer 1

不使用全局变量

所有函数参数都是全局变量，很难跟踪副作用。

如果您想在多个线程中并行使用该函数，它将失败。

只要传递参数，代码也就变得更加可读性了，因为您清楚地看到了函数执行所需的变量。

我想要的界面是：

std::string convertInfixExpressionToPostfix(std::string infixExpression);

这个函数的用户所关心的就是给出所需的输入并检索结果。

这也将使您的调用代码更加可读性：

std::cout << convertInfixExpressionToPostfix("((5+5)*(6+6))") << "\n";

不返回结果，但打印出来是另一个这样的副作用，也阻碍了重用。不是打印结果，而是将其累加到字符串中并返回它(如我建议的接口中所示)。

当然，这个接口不适合您对递归的内部需求，因此您需要另一个实现函数，它执行实际的计算，并具有更多的参数。

使用专用代码是可取的

您可以声明自己使用std::vector作为堆栈。为什么不使用std::stack，因为它有一个更清晰的接口。

可读性

不要将两个命令放在一行上，如下所示：

ops.clear(); i = 0;

这使得我们很容易忽视其中的一个。

知道何时使用交换机

您的级联ifs将更容易处理一个switch：

switch(ch) {
case '(': /*...*/ break;
case ')': /*...*/ break;
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9': /*...*/ break;
case '+':
case '-': /*...*/ break;
}

最终，您将保留if(isDigit(ch))并省略数字大小写。

不必要变量

len变量只是重复inp字符串的长度。length()方法具有恒定的时间复杂度，所以不要害怕使用它。

Answer 2

“没有人”的答案涵盖了大部分重要的事情，但还有一些可能对你有用。首先，我绝对同意全局变量必须去。有两种明显的方法可以这样做。一种方法是创建一个对象，该对象既包含现在全局的变量，又具有相关的行为。另一种方法是传递所需的变量。这种方法可能如下所示：

void convert(const std::string &inp, unsigned i, std::vector<char> &ops, std::string &out)
{
    if (i > inp.length())
        return;
    char ch = inp[i];
    if (ch == '(')
    {
        convert(inp, ++i, ops, out);
    }
    else if (ch == ')')
    {
        out.push_back(ops.back());
        ops.pop_back();
        convert(inp, ++i, ops, out);
    }
    else if (isdigit(ch))
    {
        out.push_back(ch);
        convert(inp, ++i, ops, out);
    }
    else if ((ch == '+') || (ch == '*'))
    {
        ops.push_back(ch);
        convert(inp, ++i, ops, out);
    }
}

std::string convert(const std::string inp)
{
    std::vector<char> ops;
    std::string result;
    convert(inp, 0, ops, result);
    return result;
}

请注意其他一些更改。首先，现在有两个convert例程。一个是递归版本，它有四个参数。另一个是接受单个参数的“顶级”版本，这是要转换的字符串。顶层转换还返回一个包含转换结果的字符串。

这段代码还使用ops.back()来引用ops的最后一个元素，而不是使用稍微不太明显的ops[ops.size()-1]。它在每次对i的调用中增加convert，以使一致性更易于查看，并使用std::string out作为输出，而不是直接打印到std::cout。

更微妙的重写是，原始代码有以下内容：

char ch = inp[i];
if (i > len) 

但是如果是i > len，ch只会在字符串结束后访问。这是不好的，很容易避免，只要简单地检查范围，然后使用它。

最后，您可能需要考虑如何添加额外的运算符和多位数字。这两个更改都需要对代码当前的操作方式进行一些更改。更根本的是，考虑更改代码，使其能够处理不带括号的表达式，并考虑操作符优先级。作为代码现在没有处理的两个示例，请考虑：

4+8       ==>  48+
4+8*3     ==>  483*+