Come faccio a parenthesize un'espressione di programmazione?
https://stackoverflow.com/questions/548613
-
23-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Ho un'idea per un semplice programma di fare che mi aiuterà con la precedenza degli operatori in linguaggi come C. La parte più difficile di questo è mettere tra parentesi l'espressione. Per esempio, io voglio questo:
*a.x++ = *b.x++
Convertito a questa:
((*(((a).(x))++)) = (*(((b).(x))++)))
Cosa che ho fatto manualmente in questi passaggi:
*a.x++ = *b.x++
*(a).(x)++ = *(b).(x)++
*((a).(x))++ = *((b).(x))++
*(((a).(x))++) = *(((b).(x))++)
(*(((a).(x))++)) = (*(((b).(x))++))
((*(((a).(x))++)) = (*(((b).(x))++)))
Qual è il modo migliore per ottenere questo livello di codice? C'è già una soluzione là fuori che potrei usare? Preferirei farlo in entrambi i PHP, C, C ++, Python o Ruby.
(Questo non è l'idea del mio programma, è solo il primo passo.)
Soluzione
Basta prendere un parser per la lingua selezionata, per esempio C parser , analizzare il / codice sorgente espressione e di stampa sul retro AST nel modo desiderato.
test.c:
void main(void){
int c = 2;
}
terminale:
$ 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>
>>>
Altri suggerimenti
Si sta andando ad avere bisogno di un parser di qualche tipo che capisce operatore precendenza. La versione usuale per C è Lexx / Yacc o Flex / Bison, e il modo più semplice per farlo è costruire un albero sintattico. Una volta fatto questo, solo a piedi l'albero sintattico nell'ordine "preorder" ed emettono parentesi come si entra e lasciare un nodo.
Il modo più affidabile sarà a analizzare l'espressione (tenendo conto regole di precedenza , ovviamente) e quindi elaborare l'AST risultante (Abstract Syntax Tree ) in modo top-down, l'aggiunta di parentesi come ci si sposta lungo
Come sulla conversione per postfix e valutare. Si può provare se il seguente approccio funziona. Consente di prendere * a.x ++
Operator Precedence Arguments Needed
. 3 2
++ 2 1
* 1 1
Così ora convertire l'espressione in notazione postfissa. Questo dovrebbe dare
a x . ++ *
Ora la valutazione di postfix è semplice come premere le cose in una pila, quando si colpisce un operatore, pop cima n (se necessario dall'operatore) elementi e li passano come argomenti, risultati negozio di nuovo in cima alla pila. Nel tuo caso, invece di valutare, che ci si ritorni una rappresentazione testuale del funzionamento
Stack
Read a a
Read x x
Read . (a.x)
Read ++ ((a.x)++)
Read * (*((a.x)++))
se ti aiuta, si consiglia di guardare in:
http://www.spsu.edu/cs/faculty/bbrown/web_lectures / postfix /
serie DynCalc di Bart de Smet dei messaggi
Il mio tentativo di TDDing una soluzione simile
È possibile creare un albero di espressione binario da parte degli operatori.
Credo che ci sono diversi algoritmi disponibili on-line per creare già ad albero.
Un modo semplice ho potuto pensare, è di classificare l'operatore di precedenza, e quindi dividere la stringa in 2 parti dall'operatore con la precedenza più basso prima, per poi proseguire in modo ricorsivo dividere le altre 2 parti giù più e più volte e poi alla fine, avrete l'espressione in forma di albero binario.
E poi, quando si ha l'espressione in forma di albero binario, è quindi possibile "parenthesize" dal foglie dell'albero fino alla radice.
E, naturalmente, si potrebbe compilare un parser a tutti gli effetti tramite Yacc / bisonti.
Come semplice esempio:
Exp = Term | Exp, AddOp, Term
Term = Factor | Term, MulOp, Factor
Factor = Number | Ident | PreOp, Factor | (, Exp, ) | Factor, PostOp
È possibile utilizza la grammatica di scrivere le traduzioni:
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, )
In questo caso:
a-- + b * (a+b)
si traduce in:
((a--) + (b * ((a+b))))
parsing è un argomento enorme. Dal momento che si desidera utilizzare per risolvere un problema specifico, cercare di non immergersi in tutti questi algoritmi di analisi specifiche che le persone stanno suggerendo. Piuttosto, ci sono numerosi generatori di parser, come corna o di bisonti che, data una grammatica del caso, sarà analizzare il testo e consentono di eseguire operazioni programmatiche sui componenti - come il put parentesi intorno a loro. Alcuni di questi sistemi sono dotati di grammatiche per C, o avere tali grammatiche disponibili.
ANTLR in grado di generare parser in una qualsiasi delle lingue che hai citato; vedi http://www.antlr.org/
Si possono trovare "cparen" negli archivi della vecchia net.sources newsgroup.
Se si esegue una ricerca (Google) per 'cparen', si ottiene troppo rumore, ma se si cerca per net.sources e 'cparen.c' che restringe la ricerca abbastanza per essere utile.
Ecco un sito web:
http://www.megalextoria.com/ usenet-archive / news005f3 / B14 / net / fonti / 00000360.html
Non è un archivio di shell, come mi sarei aspettato. Si presenta come un file tar di testo ASCII puro. Ci sono pochi file abbastanza che si poteva solo scompattarlo a mano.
ho scritto un programma in Python mettere tra parentesi una stringa di espressione.
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]
C'è un vecchio (1980) programma open source per fare esattamente questo. Si chiama "cparen", ma che io sia dannato se riesco a trovarlo in rete. Solo entusiasta menzioni di esso, ad esempio, 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
Se avete più fortuna di me a trovarlo, scriva
