我正在处理 R 中的嵌套表达式，需要一些帮助来编写递归函数来处理这些表达式，首先从最里面的括号开始。

给定一个字符串，如：

expr <- "(((a OR b) OR c) AND d) OR (e AND f)"

我想要执行以下替换：

  1. 将所有出现的“(i OR j)”替换为“min(1, i + j)”
  2. 将所有出现的“(i AND j)”替换为“(i * j)”

例如：

  • “(a OR b)” 应改为“min(1, a + b)”
  • “(e AND f)” 应改为 “(e * f)”

字符串“((a OR b) OR c) AND d) OR (e AND f)”的计算结果应为：

“最小（1，（最小（1，最小（1，a + b）+ c）* d）+（e * f））”

挑战在于表达式可以嵌套，我需要先处理最里面的括号，然后再向外移动。这是因为我正在编写函数来获取目标函数的用户输入，并且我有 R 代码来动态编写 Rcpp 代码…

我考虑过使用正则表达式来查找和替换模式，但递归处理嵌套结构让我陷入困境。我尝试了以下递归函数方法：


process_expr <- function(string) {
  
  # Match the innermost parentheses
  pattern <- "\\(([^()]*)\\)"
  brackets <- gregexpr(pattern, string, perl = TRUE)
  matches <- regmatches(string, brackets)
  
  # If there are no more matches, return the string
  if (length(matches[[1]]) == 0) {
    return(string)
  }
  
  # Process each match
  for (match in matches[[1]]) {
    # Apply the replacements
    modified <- gsub("\\(([^()]+) OR ([^()]+)\\)", "min(1, \\1 + \\2)", match)
    modified <- gsub("\\(([^()]+) AND ([^()]+)\\)", "(\\1 * \\2)", modified)
    
    # Replace the match in the original string
    string <- sub(pattern, modified, string, fixed = TRUE)
  }
  
  # Recurse to process the next level of nested parentheses
  return(process_expr(string))
}

# Example usage
expr <- "((a OR b) OR c) AND d) OR (e AND f)"
result <- process_expr(expr)
print(result)

上面的代码似乎无法正确处理嵌套括号，尤其是当存在多层嵌套时。我需要该函数来：

  1. 首先识别最内层的表达式。
  2. 正确应用替换件。
  3. 处理多级嵌套表达式。

我研究过的所有解决方案都适用于 Python 或 Perl，但不适用于 R。

还有其他方法可以用来获得我需要的东西吗？即

  1. 将所有出现的“(i OR j)”替换为“min(1, i + j)”
  2. 将所有出现的“(i AND j)”替换为“(i * j)”

示例数据：“(((a OR b) OR c) AND d) OR (e AND f)”

需要评估：

最小（1，（最小（1，最小（1，a + b）+ c）* d）+（e * f））

编辑：

以下是其他一些 I/O 示例：

input_2 <- "(r1 && r2) || r3 + r4 + (r5 && r6)"

输出_2：“最小（1，（r1 * r2）+ r3）+ r4）+（r6 * r7）”

以下是其他一些 I/O 示例：

input_3 <- "(r1 && r2) || (r3 && r4) + r5 || (r6 + r7)"

输出3：“最小值（1，（r1 * r2）+（r3 * r4））+最小值（1，r5 +（r6 + r7））”

2

  • 我现在无法弄清楚的主要边缘情况是：字符串 <- “(a AND b) OR (c AND d) + e” 需要评估为“min(1, (a * b) + c * d)) + e” 但下面的解决方案/答案都无法（在撰写本文时）像这样解析表达式，因为它们需要先从最里面的括号开始。


    – 


  • 1
    第二个示例的输出不正确。请注意，+优先于，||因此 (r1 && r2)|| r3 + r4 + (r5 && r6)在结构上类似于 (r1 && r2)|| (r3 + r4 + (r5 && r6))。


    – 


5 个回答
5

如果我们将输入转换为有效的 R 代码，我们可以使用解析和替换。例如，这个辅助函数可以解决问题

transform <- function(expr) {
  tx <- function(e) {
    if (is.call(e)) {
      parts <- as.list(e)
      if (parts[[1]] == quote(`%OR%`)) {
        parts[[1]] <- quote(`min`)
        parts[[3]] <- bquote(.(tx(parts[[2]])) + .(tx(parts[[3]])))
        parts[[2]] <- 1
        as.call(parts)         
      } else if (parts[[1]]==quote(`%AND%`)) {
        parts[[1]] <- quote(`*`)
        parts[[2]] <- tx(parts[[2]])
        parts[[3]] <- tx(parts[[3]])
        as.call(parts)
      } else {
        parts[-1] <- lapply(parts[-1], tx)
        as.call(parts)
      }
    } else {
      e
    }
  }
  fix <- gsub("\\bOR\\b", "%OR%", gsub("\\bAND\\b", "%AND%", expr))
  fix <- gsub("\\|\\|", "%OR%", gsub("\\&\\&", "%AND%", fix))
  deparse1(tx(str2lang(fix)))
}

我们可以用它测试

expr <- "(((a OR b) OR c) AND d) OR (e AND f)"
transform(expr)
# [1] "min(1, ((min(1, (min(1, a + b)) + c)) * d) + (e * f))"
input_2 <- "(r1 && r2) || r3 + r4 + (r5 && r6)"
transform(input_2)
# [1] "min(1, (r1 * r2) + r3) + r4 + (r5 * r6)"
input_3 <- "(r1 && r2) || (r3 && r4) + r5 || (r6 + r7)"
transform(input_3)
# [1] "min(1, (r1 * r2) + (r3 * r4)) + min(1, r5 + (r6 + r7))"

我们将 OR 和 AND 转换为 R 可以解析的%OR%and %AND%，然后遍历抽象语法树并进行转换。解析器负责构建树的艰苦工作。

5

  • 太棒了，这是一个很棒的解决方案，谢谢。这对于第一个输入示例非常有用。我不确定为什么它对 input_2 和 input_3 不起作用？


    – 

  • 1
    @statneutrino 嗯，之前你只有两个运算符，它们有明确的操作顺序/优先级。你似乎不想让加法运算符的优先级高于与/或。在这种情况下，我将其他运算符交换为优先级较低的函数。


    – 

  • 太棒了，非常感谢！我花了好几个小时才弄清楚。谢谢！


    – 

  • 1
    Op 违反了数学规则。请注意+优先于||因此 (r1 && r2)|| r3 + r4 + (r5 && r6)在结构上与 类似 (r1 && r2)|| (r3 + r4 + (r5 && r6))。


    – 

  • @Onyambu 但 OP 并未声称使用传统的数学规则。解析器可以将任意标记转换为您想要的任何语法。只要它定义明确且一致，就没问题。优先级规则可能因语言而异。


    – 

我会将文本转换为可解析的 R 代码，进行解析，通过结果调用进行递归，然后进行反解析：

(s0 <- "(((a OR b) OR c) AND d) OR (e AND f)")
## [1] "(((a OR b) OR c) AND d) OR (e AND f)"
(s1 <- gsub(" OR ", " | ", gsub(" AND ", " & ", s0)))
## [1] "(((a | b) | c) & d) | (e & f)"

recurse <- function(x) {
    if (!is.call(x))
        x
    else if ((n <- length(x)) == 3L) {
        if (identical(x[[1L]], quote(`|`)))
            call("min", 1, call("+", Recall(x[[2L]]), Recall(x[[3L]])))
        else if (identical(x[[1L]], quote(`&`)))
            call("*", Recall(x[[2L]]), Recall(x[[3L]]))
        else x
    }
    else {
        if (n >= 2L) for (i in 2L:n) x[[i]] <- Recall(x[[i]])
        x
    }    
}

(s2 <- deparse(recurse(str2lang(s1))))
## [1] "min(1, ((min(1, (min(1, a + b)) + c)) * d) + (e * f))"

1

  • 2
    哎呀，我太慢了——这个答案在结构上与之前的答案相同，但它使用的代码并不那么简单，所以也许我应该把它保留下来……？


    –      

string_parse <- function(x){
  if(is.call(x)){
    if(x[[1]] == '|') x <-  call('min', 1, call('+', x[[2]], x[[3]]))
    else if(x[[1]] == '&') x[[1]] <- as.name('*')
    x[-1] <- lapply(x[-1], string_parse)
  }
  x
}

string <- "(((a OR b) OR c) AND d) OR (e AND f)"

string_parse(str2lang(gsub("AND", "&", gsub("OR", "|", string))))
min(1, ((min(1, (min(1, a + b)) + c)) * d) + (e * f))

尝试使用字符串替换：

string <- "(((a OR b) OR c) AND d) OR (e AND f)"

# function to substitute a single expression
process_expression <- function(expression) {
  # check if expression is something OR something, or something AND something, with optional parentheses
  if(grepl("^[^()]+\\s+(?:OR|AND)\\s+[^()]+$", expression) || grepl("^\\([^()]+\\s+(?:OR)|(?:AND)\\s+[^()]+\\)$", expression)) {
    # convert to required output, using braces {} to avoid clashes with the () in string
    result <- gsub("\\(?([^()]+)\\s+OR\\s+([^()]+)\\)?", "min{1, \\1 + \\2}", expression)
    result <- gsub("\\(?([^()]+)\\s+AND\\s+([^()]+)\\)?", "{\\1 * \\2}", result)
  } else {
    stop("Invalid expression")
  }
  return(result)
}

# function to find and replace all expressions in a string
process_string <- function(string) {
  # find the (innermost) expressions
  match_data <- gregexpr("\\(?[^()]+\\s+(?:OR|AND)\\s+[^()]+\\)?", string)
  # get the match strings
  matches <- regmatches(string, match_data)[[1]]
  # substitute the matches for their processed equivalents
  result <- Reduce(\(s, m) gsub(m, process_expression(m), s, fixed = TRUE), matches, init=string)
  # recurse if any AND or OR remain
  if(grepl("(AND|OR)", result)) {
    result <- process_string(result)
  }
  # change braces back to parentheses
  result <- gsub("{", "(", gsub("}", ")", result, fixed = TRUE), fixed = TRUE)
  
  return(result)
}

process_string(string)
#> [1] "min(1, (min(1, min(1, a + b) + c) * d) + (e * f))"

创建于 2024-06-24，使用

如果 ，条件是否必须OR求值为 1 TRUE？或者换句话说，在 和 都为 的情况下，如果 求值为 2 （从逻辑上讲仍然是 ）可以吗？如果是(A OR B)这样，一个非常简单的解决方案如下：TRUEABTRUE

gsub(" +AND +"," * ",gsub(" +OR +"," + ",expr))

请注意，这还会处理您可能意外添加在OR/AND表达式周围的任何额外空格。

编辑：此外，正如另一位用户在您的问题下方的评论中提到的那样，您在开头缺少一个括号expr。

2

  • 非常感谢您的回答。是的，不幸的是我要求答案是 1 或总和。虽然我刚刚意识到，也许我可以除以 2？


    – 

  • 这太糟糕了，而且我担心如果你除以 2，你将会不幸遇到同样的问题，当只有一个或A时B，TRUE因为你的结果将是 0.5（加上上面的表达式不会那么简单）。


    –