如何为表达式添加括号？

Question

我有一个想法，可以制作一个简单的程序，它将帮助我处理 C 等语言中的运算符优先级。其中最困难的部分是为表达式加上括号。 例如，我想要这个：

*a.x++ = *b.x++

转换为：

((*(((a).(x))++)) = (*(((b).(x))++)))

我在这些步骤中手动完成的：

           *a.x++ = *b.x++
       *(a).(x)++ = *(b).(x)++
     *((a).(x))++ = *((b).(x))++
   *(((a).(x))++) = *(((b).(x))++)
 (*(((a).(x))++)) = (*(((b).(x))++))
((*(((a).(x))++)) = (*(((b).(x))++)))

完成此操作的最佳方法是什么？ 已经有我可以使用的解决方案了吗？ 我更喜欢使用 PHP、C、C++、Python 或 Ruby 来完成此操作。

（这不是我的程序的全部想法，这只是第一步。）

Answer 1

最可靠的方法是解析表达式（考虑到account 优先级规则，当然），然后在 a 中处理生成的 AST（抽象语法树）自上而下的方式，在前进时添加括号

Answer 2

转换为后缀并评估怎么样？
您可以尝试以下方法是否有效。
让我们以 *a.x++

Operator    Precedence  Arguments Needed
.           3               2
++          2               1
*           1               1

为例，现在将表达式转换为后缀表示法。 现在，对

a x . ++ *

后缀的评估就像将东西推入堆栈一样简单，当您点击运算符时，弹出前 n 个（根据运算符需要的）元素并将它们作为参数传递，将结果存储回堆栈。
在您的情况下，您将返回操作的文本表示（

        Stack
Read a      a
Read x      x
Read .      (a.x)
Read ++     ((a.x)++)
Read *      (*((a.x)++))

如果有帮助），而不是进行评估，您可能需要查看：
http://www.spsu.edu/cs/faculty/bbrown/web_lectures /后缀/
Bart de smet 的 DynCalc 系列帖子
我尝试 TDD 类似的解决方案

Answer 3

只需选择适合您所选语言的解析器，例如 C 解析器，解析表达式/源代码并以您想要的方式打印 AST。

测试.c：

void main(void){
    int c = 2;
}

终端：

$ python
>>> import pycparser
>>> test = pycparser.parse_file('test.c')
>>> test.show()
FileAST: 
  FuncDef: 
    Decl: main, [], []
      FuncDecl: 
        ParamList: 
          Typename: []
            TypeDecl: None, []
              IdentifierType: ['void']
        TypeDecl: main, []
          IdentifierType: ['void']
    Compound: 
      Decl: c, [], []
        TypeDecl: c, []
          IdentifierType: ['int']
        Constant: int, 2
>>> for node in test.ext:
...     print node
...
<pycparser.c_ast.FuncDef object at 0x7fe1436db750>
>>>

Answer 4

您可以从运算符创建二叉表达式树。

我相信网上已经有几种算法可以创建这样的树。

我能想到的一种简单方法是按优先级对运算符进行排序，然后首先按优先级最低的运算符将字符串分成两部分，然后继续递归地一遍又一遍地向下拆分其他两部分，最后，你将会有二叉树形式的表达式。

然后，当您拥有二叉树形式的表达式时，您可以从树的叶子到根“加括号”。

当然，您可以通过 yacc/bison 编译一个成熟的解析器。

Answer 5

举一个简单的例子：

Exp = Term | Exp, AddOp, Term 
Term = Factor | Term, MulOp, Factor
Factor = Number | Ident | PreOp, Factor | (, Exp, ) | Factor, PostOp

您可以使用语法来编写翻译：

Exp    = Term                    -> Term
       | Exp, AddOp, Term        -> (, Exp, AddOp, Term, )
Term   = Factor                  -> Factor
       | Term, MulOp, Factor     -> (, Term, MulOp, Factor, )
Factor = Number                  -> Number
       | Ident                   -> Ident
       | PreOp, Factor           -> (, PreOp, Factor, )
       | (, Exp, )               -> (, Exp, )
       | Factor, PostOp          -> (, Factor, PostOp, )

在这种情况下：

a-- + b * (a+b) 

翻译为：

((a--) + (b * ((a+b))))

Answer 6

解析是一个很大的话题。 由于您只是想用它来解决特定问题，因此请尽量不要沉浸在人们建议的所有这些特定解析算法中。 相反，有许多解析器生成器，例如 antler 或 bison，在给定适当的语法的情况下，它们将解析文本并允许您对组件执行编程操作 - 例如在它们周围添加括号。 其中一些系统附带了 C 语法，或者具有可用的此类语法。

antlr 可以生成您提到的任何语言的解析器； 请参阅http://www.antlr.org/

Answer 7

您可以在旧的 net.sources 新闻组的档案中找到“cparen”。

如果您搜索（Google）“cparen”，您会得到太多噪音，但如果您搜索
对于 net.sources 和 'cparen.c'，它缩小了搜索范围，足以发挥作用。

这是一个网站：

http://www.megalextoria。 com/usenet-archive/news005f3/b14/net/sources/00000360.html

正如我所期望的那样，它不是一个 shell 存档。
它看起来像一个纯 ASCII 文本 tar 文件。
文件数量足够少，您可以
用手拆开包装。

Answer 8

我用 Python 编写了一个程序来为表达式字符串添加括号。

def pref(op):
    print "called with op", op
    ret = -1
    if op == '+':
        print "matched +"
        ret = 1
    if op == '-':
        print "matched -"
        ret = 2
    if op == '*':
        print "matched *"
        ret = 3
    if op == '/':
        print "matched /"
        ret = 4

    return ret

def evaluate(expr, operand_stack, operator_stack):
    print "**In evaluate**"
    print operator_stack
    print operand_stack

    expr1 = operand_stack.pop()
    expr2 = operand_stack.pop()
    op    = operator_stack.pop()

    # Parenthesize the expression
    expr = "(" + expr2 + op + expr1 + ")"
    print "expr1", expr1
    print "expr2", expr2
    print "expr", expr

    # Push the result back on the stack
    operand_stack.append(expr)

    print operator_stack
    print operand_stack
    print "**Out evaluate**"
    return expr

def looper(str, expr, operator_stack, operand_stack):
    l = 0
    cnt = len(str)

    # Loop over the input string
    while  l < cnt:
        if str[l] in ('+', '-', '*', '/'):
            print "operator found: op, index", str[l], l
            print operator_stack, len(operator_stack)

            x = len(operator_stack) - 1
            if x > 0:
                print "Comparing:", operator_stack[x], str[l]

                # If op on stack has higher preference than the op in question
                if (pref(operator_stack[x]) > pref(str[l])):
                    expr = evaluate(expr, operand_stack, operator_stack)
            operator_stack.append(str[l])
        else:
            # Add the operand to operand stack
            operand_stack.append(str[l])
        l += 1

    print operator_stack
    print operand_stack

    print "Take care of last elements"
    op_cnt = len(operator_stack)
    while op_cnt:
        expr = evaluate(expr, operand_stack, operator_stack)
        op_cnt -= 1

    print operator_stack
    print operand_stack

if __name__ == '__main__':
    str = "a+c*d-e/w*x+a-s"
    cnt = len(str)

    operand_stack  = []
    operator_stack  = []
    expr = ""
    looper(str, expr, operator_stack, operand_stack)

    print "Output=>", operand_stack[0]

Answer 9

有一个非常古老的（1980 年代）开源程序可以做到这一点。
它叫“cparen”，但如果我能在网上找到它，我就该死了。 只有热情地提到它，例如
https://groups.google.com /group/comp.lang.c/tree/browse_frm/month/1990-03/1583b4728a6d94db
http://www.language-c.info/re-should-i-capitalize-const-identifiers

如果你比我更幸运地找到它，请写

Answer 10

您将需要某种能够理解运算符优先级的解析器。 C 的常用版本是 Lexx/Yacc 或 flex/bison，最简单的方法是构造一个解析树。 完成此操作后，只需按“预序”顺序遍历解析树，并在进入和离开节点时发出括号。