c++ - 前缀(抛光)表示法 - 评估 C++

Question

我正在寻找使用递归解析前缀表达式的代码。主要使用 C++，但也可以使用其他语言，我会翻译。谢谢。

Answer 1

自己做真的很容易(您只需要一个运算符堆栈(有时/可选地是它的第一项))。

但如果你真的不想做太多工作，这里有一个链接:

prefix notation string to int conversion

如果您需要使用递归，您基本上将函数中的局部变量用作堆栈中的单个元素。

例如。伪C++代码如下:

int naughtyglobalendindex = 0;
int parse(string str) {

  if (/* str starts off with an integer */) return the integer;

  char operator;
  operator = ?? // you will need to get the first op here. Maybe sscanf(str,"%c",&operator) or similar

  // get first argument
  int first = parse(/* str with 1st operator removed */);
  // get 2nd integer argument
  int second = parse(/* str - get substring from naughtyglobalendindex to end*/)

  // return first operator second <- this is pseudocode
  // in effect you want a switch clause
  switch (operator) {
    case '+': return first + second;
    case '-': return first - second; // and so on
  }
}

您可以将伪代码转换为实际的 C++，如果需要，还可以修复全局 naughtyglobalendindex 变量。