
数学的表現と論理演算を含む文字列を解析し、その結果を評価する問題について考えます。この問題では、整数、加算・減算の算術演算、および論理演算(AND、OR、NOT)が含まれる文字列を扱います。これらの演算を正しく解析し、優先順位に従って評価することが求められます。
1. 問題の理解
まず、与えられた文字列がどのような形式であるかを理解します。例えば、以下のような文字列が与えられたとします。
3 + 5 AND 2 OR NOT 1 - 4
この文字列には、整数(3, 5, 2, 1, 4)、算術演算(+、-)、および論理演算(AND、OR、NOT)が含まれています。これらの演算は、以下の優先順位で評価されます。
- NOT
- 算術演算(+、-)
- AND
- OR
2. 文字列のトークン化
まず、文字列をトークン(最小の意味単位)に分割します。トークンは、整数、演算子、または論理演算子です。例えば、上記の文字列は以下のトークンに分割されます。
['3', '+', '5', 'AND', '2', 'OR', 'NOT', '1', '-', '4']
3. トークンの解析
次に、トークンを解析して、数値と演算子を区別します。数値は整数として扱い、演算子は算術演算または論理演算として扱います。
4. 優先順位に従った評価
トークンを解析した後、優先順位に従って評価を行います。優先順位は以下の通りです。
- NOT
- 算術演算(+、-)
- AND
- OR
この順序で演算を評価することで、正しい結果を得ることができます。
5. 実装
以下に、上記の手順を実装したPythonコードを示します。
def evaluate_expression(expression):
import re
from collections import deque
# トークン化
tokens = re.findall(r'\d+|AND|OR|NOT|[+-]', expression)
# 優先順位に従って評価
def evaluate(tokens):
stack = []
i = 0
while i < len(tokens):
token = tokens[i]
if token == 'NOT':
# NOT演算を評価
value = int(tokens[i+1])
stack.append(not value)
i += 2
elif token in ('+', '-'):
# 算術演算を評価
op = token
value1 = stack.pop()
value2 = int(tokens[i+1])
if op == '+':
stack.append(value1 + value2)
else:
stack.append(value1 - value2)
i += 2
elif token == 'AND':
# AND演算を評価
value1 = stack.pop()
value2 = int(tokens[i+1])
stack.append(value1 and value2)
i += 2
elif token == 'OR':
# OR演算を評価
value1 = stack.pop()
value2 = int(tokens[i+1])
stack.append(value1 or value2)
i += 2
else:
# 数値をスタックにプッシュ
stack.append(int(token))
i += 1
return stack[0]
return evaluate(tokens)
# テスト
expression = "3 + 5 AND 2 OR NOT 1 - 4"
result = evaluate_expression(expression)
print(f"Result: {result}")
6. 関連する質問と回答
Q1: なぜNOT演算が最初に評価されるのですか?
A1: NOT演算は単項演算子であり、他の演算よりも優先順位が高いため、最初に評価されます。
Q2: 算術演算と論理演算の優先順位はどのように決められていますか?
A2: 一般的に、算術演算は論理演算よりも優先順位が高く、NOT > 算術演算 > AND > OR の順で評価されます。
Q3: このコードはどのようにトークンを分割していますか?
A3: 正規表現を使用して、数値、演算子、論理演算子をトークンとして分割しています。
Q4: このコードはどのようにして優先順位を実装していますか?
A4: トークンを順番に処理し、優先順位に従ってスタックを使用して演算を評価しています。
Q5: このコードはどのような入力に対応していますか?
A5: このコードは、整数、加算・減算の算術演算、および論理演算(AND、OR、NOT)を含む文字列に対応しています。