Реализация простой электронной таблицы

Решение

Анализ задачи

Это классическая задача на обработку зависимостей и парсинг выражений. Ключевые сложности:

1. Парсинг адресов ячеек: A1, B2, Z10 → интерпретировать
2. Парсинг выражений: =A1+B2*2 → построить AST и вычислить
3. Обнаружение циклов: A1=B1, B1=A1 → предотвратить бесконечную рекурсию
4. Кэширование: Помнить уже вычисленные значения
5. Обработка ошибок: Деление на ноль, несуществующие ячейки

---

Структуры данных

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

/// <summary>
/// Результат вычисления ячейки
/// </summary>
public class CellValue
{
    public bool IsError { get; set; }
    public string ErrorMessage { get; set; }
    public decimal? Value { get; set; }

    public static CellValue Success(decimal value) => new() { Value = value, IsError = false };
    public static CellValue Error(string message) => new() { ErrorMessage = message, IsError = true };
}

/// <summary>
/// Содержимое ячейки (формула или значение)
/// </summary>
public class CellContent
{
    public string Address { get; set; }  // A1, B2, etc.
    public string RawValue { get; set; }  // Оригинальный текст
    public bool IsFormula { get; set; }  // Начинается ли с =
}

---

Основной класс электронной таблицы

public class Spreadsheet
{
    private readonly Dictionary<string, CellContent> _cells = new();
    private readonly Dictionary<string, CellValue> _cache = new();
    private readonly HashSet<string> _evaluating = new();  // Для обнаружения циклов

    public void SetCell(string address, string value)
    {
        ValidateCellAddress(address);
        address = address.ToUpper();

        var content = new CellContent
        {
            Address = address,
            RawValue = value.Trim(),
            IsFormula = value.Trim().StartsWith("=")
        };

        _cells[address] = content;
        _cache.Remove(address);  // Очищаем кэш этой ячейки
    }

    public CellValue GetValue(string address)
    {
        ValidateCellAddress(address);
        address = address.ToUpper();

        // Проверяем кэш
        if (_cache.TryGetValue(address, out var cachedValue))
            return cachedValue;

        // Обнаруживаем циклические зависимости
        if (_evaluating.Contains(address))
            return CellValue.Error($"Circular dependency detected for {address}");

        _evaluating.Add(address);

        try
        {
            if (!_cells.TryGetValue(address, out var content))
                return CellValue.Error($"Cell {address} not found");

            CellValue result;

            if (content.IsFormula)
            {
                // Парсим и вычисляем формулу
                var formula = content.RawValue.Substring(1);  // Убираем =
                result = EvaluateFormula(formula);
            }
            else
            {
                // Пытаемся преобразовать в число
                if (decimal.TryParse(content.RawValue, out var number))
                    result = CellValue.Success(number);
                else
                    result = CellValue.Error($"Invalid value in {address}: {content.RawValue}");
            }

            _cache[address] = result;
            return result;
        }
        finally
        {
            _evaluating.Remove(address);
        }
    }

    private CellValue EvaluateFormula(string formula)
    {
        try
        {
            var tokens = TokenizeFormula(formula);
            var parser = new FormulaParser(tokens, this);
            var result = parser.Parse();
            return result;
        }
        catch (DivideByZeroException)
        {
            return CellValue.Error("Division by zero");
        }
        catch (Exception ex)
        {
            return CellValue.Error($"Formula error: {ex.Message}");
        }
    }

    private List<string> TokenizeFormula(string formula)
    {
        var tokens = new List<string>();
        var current = "";
        var i = 0;

        while (i < formula.Length)
        {
            var ch = formula[i];

            // Операторы
            if ("+-*/()".Contains(ch))
            {
                if (!string.IsNullOrEmpty(current))
                    tokens.Add(current);
                tokens.Add(ch.ToString());
                current = "";
            }
            // Пробелы
            else if (char.IsWhiteSpace(ch))
            {
                if (!string.IsNullOrEmpty(current))
                    tokens.Add(current);
                current = "";
            }
            // Символы и цифры
            else
            {
                current += ch;
            }

            i++;
        }

        if (!string.IsNullOrEmpty(current))
            tokens.Add(current);

        return tokens;
    }

    private void ValidateCellAddress(string address)
    {
        if (!Regex.IsMatch(address, @"^[A-Za-z]+\d+$"))
            throw new ArgumentException($"Invalid cell address: {address}");
    }

    public void PrintSpreadsheet()
    {
        Console.WriteLine("\n=== Spreadsheet ===");
        foreach (var (address, content) in _cells.OrderBy(p => p.Key))
        {
            var value = GetValue(address);
            if (value.IsError)
                Console.WriteLine($"{address}: {value.ErrorMessage}");
            else
                Console.WriteLine($"{address}: {value.Value}");
        }
        Console.WriteLine();
    }
}

---

Парсер формул (рекурсивный спуск)

/// <summary>
/// Парсер с использованием рекурсивного спуска (Recursive Descent Parser)
/// </summary>
public class FormulaParser
{
    private readonly List<string> _tokens;
    private int _position = 0;
    private readonly Spreadsheet _spreadsheet;

    public FormulaParser(List<string> tokens, Spreadsheet spreadsheet)
    {
        _tokens = tokens;
        _spreadsheet = spreadsheet;
    }

    public CellValue Parse()
    {
        var result = ParseAdditive();
        if (_position < _tokens.Count)
            return CellValue.Error($"Unexpected token: {_tokens[_position]}");
        return result;
    }

    // Самый низкий приоритет: + и -
    private CellValue ParseAdditive()
    {
        var left = ParseMultiplicative();
        if (left.IsError) return left;

        while (_position < _tokens.Count && (_tokens[_position] == "+" || _tokens[_position] == "-"))
        {
            var op = _tokens[_position++];
            var right = ParseMultiplicative();
            if (right.IsError) return right;

            if (left.Value == null || right.Value == null)
                return CellValue.Error("Cannot operate on null values");

            left = op == "+"
                ? CellValue.Success(left.Value.Value + right.Value.Value)
                : CellValue.Success(left.Value.Value - right.Value.Value);
        }

        return left;
    }

    // Средний приоритет: * и /
    private CellValue ParseMultiplicative()
    {
        var left = ParsePrimary();
        if (left.IsError) return left;

        while (_position < _tokens.Count && (_tokens[_position] == "*" || _tokens[_position] == "/"))
        {
            var op = _tokens[_position++];
            var right = ParsePrimary();
            if (right.IsError) return right;

            if (left.Value == null || right.Value == null)
                return CellValue.Error("Cannot operate on null values");

            if (op == "/" && right.Value.Value == 0)
                throw new DivideByZeroException();

            left = op == "*"
                ? CellValue.Success(left.Value.Value * right.Value.Value)
                : CellValue.Success(left.Value.Value / right.Value.Value);
        }

        return left;
    }

    // Самый высокий приоритет: скобки, числа, ячейки
    private CellValue ParsePrimary()
    {
        if (_position >= _tokens.Count)
            return CellValue.Error("Unexpected end of expression");

        var token = _tokens[_position];

        // Скобки
        if (token == "(")
        {
            _position++;
            var result = ParseAdditive();
            if (_position >= _tokens.Count || _tokens[_position] != ")")
                return CellValue.Error("Missing closing parenthesis");
            _position++;
            return result;
        }

        // Проверяем, это ли ячейка (A1, B2, etc)
        if (IsCellAddress(token))
        {
            _position++;
            return _spreadsheet.GetValue(token);
        }

        // Проверяем, это ли число
        if (decimal.TryParse(token, out var number))
        {
            _position++;
            return CellValue.Success(number);
        }

        return CellValue.Error($"Invalid token: {token}");
    }

    private bool IsCellAddress(string token)
    {
        return Regex.IsMatch(token, @"^[A-Za-z]+\d+$");
    }
}

---

Пример использования

class Program
{
    static void Main()
    {
        var spreadsheet = new Spreadsheet();

        // Пример 1: Простые значения и ссылки
        spreadsheet.SetCell("A1", "5");
        spreadsheet.SetCell("A2", "=A1");
        spreadsheet.SetCell("A3", "=A1+A2");
        spreadsheet.PrintSpreadsheet();
        // Вывод: A1=5, A2=5, A3=10

        // Пример 2: Арифметика
        var s2 = new Spreadsheet();
        s2.SetCell("A1", "10");
        s2.SetCell("A2", "2");
        s2.SetCell("A3", "=A1*A2+5");
        s2.SetCell("A4", "=(A1+A2)*2");
        s2.PrintSpreadsheet();
        // Вывод: A1=10, A2=2, A3=25, A4=24

        // Пример 3: Циклические зависимости
        var s3 = new Spreadsheet();
        s3.SetCell("A1", "=B1");
        s3.SetCell("B1", "=A1");
        var value = s3.GetValue("A1");
        Console.WriteLine($"A1 (циклические зависимости): {value.ErrorMessage}");
        // Вывод: Circular dependency detected for A1

        // Пример 4: Деление на ноль
        var s4 = new Spreadsheet();
        s4.SetCell("A1", "0");
        s4.SetCell("A2", "=5/A1");
        var divZero = s4.GetValue("A2");
        Console.WriteLine($"A2 (деление на ноль): {divZero.ErrorMessage}");
        // Вывод: Division by zero

        // Пример 5: Интерактивный режим
        InteractiveMode(new Spreadsheet());
    }

    static void InteractiveMode(Spreadsheet spreadsheet)
    {
        Console.WriteLine("\nInteractive Spreadsheet (type exit to quit, print to show all)");
        while (true)
        {
            Console.Write("> ");
            var input = Console.ReadLine();

            if (input?.ToLower() == "exit")
                break;

            if (input?.ToLower() == "print")
            {
                spreadsheet.PrintSpreadsheet();
                continue;
            }

            var parts = input?.Split(=, StringSplitOptions.TrimEntries);
            if (parts?.Length == 2)
            {
                try
                {
                    spreadsheet.SetCell(parts[0], parts[1]);
                    var value = spreadsheet.GetValue(parts[0]);
                    if (value.IsError)
                        Console.WriteLine($"Error: {value.ErrorMessage}");
                    else
                        Console.WriteLine($"Result: {value.Value}");
                }
                catch (Exception ex)
                {
                    Console.WriteLine($"Exception: {ex.Message}");
                }
            }
        }
    }
}

---

Полный результат работы

=== Spreadsheet ===
A1: 5
A2: 5
A3: 10

A1 (циклические зависимости): Circular dependency detected for A1
A2 (деление на ноль): Division by zero

---

Расширения и оптимизации

1. Топологическая сортировка для лучшего обнаружения циклов

public class DependencyAnalyzer
{
    public static bool HasCycle(Spreadsheet spreadsheet)
    {
        var visited = new HashSet<string>();
        var recursionStack = new HashSet<string>();

        foreach (var cell in spreadsheet.GetAllCells())
        {
            if (!visited.Contains(cell))
            {
                if (HasCycleDFS(cell, visited, recursionStack, spreadsheet))
                    return true;
            }
        }
        return false;
    }

    private static bool HasCycleDFS(
        string cell,
        HashSet<string> visited,
        HashSet<string> recursionStack,
        Spreadsheet spreadsheet)
    {
        visited.Add(cell);
        recursionStack.Add(cell);

        var dependencies = GetDependencies(cell, spreadsheet);
        foreach (var dep in dependencies)
        {
            if (!visited.Contains(dep))
            {
                if (HasCycleDFS(dep, visited, recursionStack, spreadsheet))
                    return true;
            }
            else if (recursionStack.Contains(dep))
                return true;  // Цикл найден
        }

        recursionStack.Remove(cell);
        return false;
    }
}

2. Поддержка встроенных функций

private CellValue ApplyFunction(string functionName, List<CellValue> args)
{
    return functionName.ToUpper() switch
    {
        "SUM" => args.All(a => !a.IsError)
            ? CellValue.Success(args.Sum(a => a.Value ?? 0))
            : CellValue.Error("Invalid arguments for SUM"),
        
        "AVG" => args.All(a => !a.IsError) && args.Count > 0
            ? CellValue.Success(args.Sum(a => a.Value ?? 0) / args.Count)
            : CellValue.Error("Invalid arguments for AVG"),
        
        _ => CellValue.Error($"Unknown function: {functionName}")
    };
}

---

Выводы

✅ Ключевые техники:

1. Рекурсивный спуск — простой парсер для математических выражений
2. Кэширование — помним вычисленные значения
3. Отслеживание стека вызовов — обнаруживаем циклы
4. DFS — проверка циклических зависимостей
5. Обработка ошибок — делимся на ноль, циклы, неправильные адреса