我有一个简单的程序可以帮助我在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中执行此操作。
((这不是我程序的整体思想,只是第一步。)
只需为您选择的语言选择一个解析器,例如C parser,解析表达式/源代码,然后以所需的方式将AST打印回来。
test.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>
>>>
[有一个非常古老的(1980年代)开源程序可以做到这一点。它被称为“ cparen”,但是如果我可以在网上找到它,那该死的。仅热情地提及它,例如https://groups.google.com/group/comp.lang.c/tree/browse_frm/month/1990-03/1583b4728a6d94dbhttp://www.language-c.info/re-should-i-capitalize-const-identifiers
如果您比我幸运的话,请写
您将需要某种能够理解运算符优先级的解析器。 C的通常版本是Lexx / Yacc或flex / bison,最简单的方法是构造一个解析树。完成此操作后,只需按“预订”顺序遍历解析树,并在进入和离开节点时发出解析。
最可靠的方法是到parse the expression(当然要考虑precedence rules,然后以自上而下的方式处理生成的AST(抽象语法树),并在移动时加上括号]
如何转换为后缀并进行评估。您可以尝试以下方法是否有效?让我们来* 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/postfix/Bart de smet's DynCalc series of postsMy attempt at TDDing a similar solution
您可以从运算符创建一个二进制表达式树。
我相信已经有几种在线算法可以创建这种树。
我可以想到的一种简单方法是,按优先级对运算符进行排序,然后由优先级最低的运算符将字符串分成两部分,然后继续递归地将其他两部分一遍又一遍地分解,最后,您将获得二叉树形式的表达式。
然后,当您具有二叉树形式的表达式时,您可以从树的叶子到根“向上放大”。
当然,您可以通过yacc / bison编译完整的解析器。
作为一个简单的例子:
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))))
解析是一个巨大的话题。由于您只想使用它来解决特定问题,因此请不要沉迷于人们建议的所有这些特定解析算法中。相反,有许多解析器生成器,例如鹿角或野牛,如果给出了适当的语法,它们就会解析文本并允许您对组件执行编程操作-例如在它们周围加上括号。其中一些系统带有C语法,或者有可用的语法。
antlr可以使用您提到的任何语言生成解析器;参见http://www.antlr.org/
您可以在旧的net.sources新闻组的档案中找到“ cparen”。
[如果您在(Google)中搜索“ cparen”,则会产生过多的噪音,但是如果您搜索net.sources和'cparen.c'可以将搜索范围缩小到足够有用。
这里是一个网站:
http://www.megalextoria.com/usenet-archive/news005f3/b14/net/sources/00000360.html
这不是我所期望的shell存档。它看起来像一个纯ASCII文本tar文件。文件太少,您只能用手打开包装。
[我用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]