Question

PYTHON
Задание на Tree
Напишите программу, которая вычисляет значение арифметического выражения, записанного в виде символьной строки. В выражении используются только целые числа и знаки арифметических операций (+-*/). Результат операции деления – целое число.


Входные данные


На вход программы поступает символьная строка, содержащая правильную запись арифметического выражения.


Выходные данные

Программа должна вывести значение переданного ей выражения как целое число.

Примеры
входные данные
125-6-73/5*8
выходные данные
7

Answer 1

Для розв'язання цього завдання можна використати структуру даних "дерево" для представлення арифметичного виразу і обчислення його значення. Ось програма на Python, яка вирішує це завдання:

class Node:

   def __init__(self, value):

       self.value = value

       self.left = None

       self.right = None

def build_expression_tree(expression):

   tokens = expression.split()

   stack = []

   

   for token in tokens:

       if token.isdigit() or (token[0] == '-' and token[1:].isdigit()):

           stack.append(Node(int(token)))

       else:

           node = Node(token)

           node.right = stack.pop()

           node.left = stack.pop()

           stack.append(node)

   

   return stack[0]

def evaluate_expression_tree(root):

   if root.value.isdigit() or (root.value[0] == '-' and root.value[1:].isdigit()):

       return int(root.value)

   

   left_value = evaluate_expression_tree(root.left)

   right_value = evaluate_expression_tree(root.right)

   

   if root.value == '+':

       return left_value + right_value

   elif root.value == '-':

       return left_value - right_value

   elif root.value == '*':

       return left_value * right_value

   elif root.value == '/':

       return left_value // right_value

def main():

   expression = input("Введіть арифметичне виразення: ")

   root = build_expression_tree(expression)

   result = evaluate_expression_tree(root)

   print("Результат обчислення: ", result)

if __name__ == "__main__":

   main()

Ця програма будує дерево виразу, а потім обчислює його значення. Вхідні дані подаються через введення з клавіатури, а результат виводиться на екран. Для вашого прикладу вхідна строка "125-6-73/5*8" повинна вивести результат "7".