数式から不要なカッコを取り除く方法

質問

下記のように数式を与えると、不要なカッコを取り除いた式を返すようなプログラムを作りたいと思っています。
---
(1) A+B+(C*D)+E → A+B+C*D+E
(2) ((A*B)*C)/D/E → A*B*C/D/E
(3) ((A+B)*C)*D*E → (A+B)*C*D*E

VBA、UNIXのシェルあたりで実装できないか検討しています。
いい実装方法があれば教えてください。

よろしくお願いします。

回答No.3

sakusaker7

質問にある程度ならまじめに構文解析せんでもよかろうと
試しにやってみたらおおはまり。

まあロジックの参考にでもなればと思い貼り付けておきます。

#
#coding: sjis
#下記のように数式を与えると、不要なカッコを取り除いた式を返すようなプログラムを作りたいと思っています。
#---
#(1) A+B+(C*D)+E → A+B+C*D+E
#(2) ((A*B)*C)/D/E → A*B*C/D/E
#(3) ((A+B)*C)*D*E → (A+B)*C*D*E
#
#VBA、UNIXのシェルあたりで実装できないか検討しています。
#いい実装方法があれば教えてください。
#
#よろしくお願いします。

def make_stream(s):
____return iter(list(s))

def reduce_paren(inp):
____#tok = inp.next()
____OPS = "+-*/"
____op_stack = []
____result = []

____def reduce_paren_sub1():
________r = []
________while True:
____________try:
________________tok = inp.next()
____________except :
________________break

____________if tok == '(':
________________r.append(reduce_paren_sub1())
____________elif tok == ')':
________________return r
____________elif tok in OPS:
________________r.append(tok)
____________else:
________________r.append(tok)

________return r

____def get_lowest_order_op(l):
________op = l[1]
________for i in l[3::2]:
____________if op in list("*/") and i in list("+-"):
________________op = i
________return op

____def reduce_paren_sub2(inp):
________r = []
________while True:
____________try:
________________term = inp.next()
____________except :
________________break

____________if isinstance(term, list):
________________r2 = reduce_paren_sub2(iter(term))
________________op = get_lowest_order_op(r2)
________________if op_stack[-1] in list("*/") and op in list("+-"):
____________________r.append(op_stack[-1])
____________________r.append(term)
________________else:
____________________op2 = inp.next()
____________________if op in list("*/"):
________________________for i in r2:
____________________________r.append(i)
____________________else:
________________________r.append(r2)
____________________r.append(op2)
____________________op_stack.append(op2)
____________else:
________________if term in OPS:
____________________op_stack.append(term)
________________r.append(term)
________return r

____tmp = reduce_paren_sub1()
____inp2 = iter(tmp)
____result = reduce_paren_sub2(inp2)
____return result
____
sampledata = [
____"A+B+(C*D)+E",
____"((A*B)*C)/D/E",
____"((A+B)*C)*D*E"
]

for s in sampledata:
____print "input =", s
____inp = make_stream(s)
____print "output = ", reduce_paren(inp)
____print "####\n\n"

pythonスクリプトなので、行頭のインデントのための空白を
'_' で置き換えてますのでよろしく。

実行結果:
input = A+B+(C*D)+E
output = ['A', '+', 'B', '+', 'C', '*', 'D', '+', 'E']
####

input = ((A*B)*C)/D/E
output = ['A', '*', 'B', '*', 'C', '/', 'D', '/', 'E']
####

input = ((A+B)*C)*D*E
output = [['A', '+', 'B'], '*', 'C', '*', 'D', '*', 'E']
####

回答No.2

nitorin

yacc & lex　という選択肢もあります。

参考URL：

http://kmaebashi.com/programmer/devlang/yacclex.html

回答No.1

Oh-Orange

★アドバイス
・『数式』を評価できるようにプログラミングします。
　VBA、または VBScript などで実装できると思います。
　問題は評価させるロジック(アルゴリズム)ですね。
・次のリンクをどうぞ。
　http://www.tuat.ac.jp/~tuatmcc/contents/monthly/200206/nuki.xml
　数式を評価するには
　(1)カッコを評価
　(2)乗算・除算を評価
　(3)加算・減算を評価
　となります。
　数字が小さいほど優先順位が高いことになります。
　再帰処理すれば楽になります。
　つまり、カッコ内の加算・減算は(3)の評価関数を呼ぶ。
・以上。

参考URL：

http://www.tuat.ac.jp/~tuatmcc/contents/monthly/200206/nuki.xml