Язык Си в примерах/Задача «Расчёт сопротивления схемы»

Язык Си в примерах


  1. Компиляция программ
  2. Простейшая программа «Hello World»
  3. Учимся складывать
  4. Максимум
  5. Таблица умножения
  6. ASCII-коды символов
  7. Верхний регистр
  8. Скобочки
  9. Факториал
  10. Степень числа
  11. Треугольник Паскаля
  12. Корень уравнения
  13. Система счисления
  14. Сортировка
  15. Библиотека complex
  16. Сортировка на основе qsort
  17. RPN-калькулятор
  18. RPN-калькулятор на Bison
  19. Простая грамматика
  20. Задача «Расчёт сопротивления схемы»
  21. Простая реализация конечного автомата
  22. Использование аргументов командной строки
  23. Чтение и печать без использования stdio
  24. Декодирование звукозаписи в формате ADX
  25. Другие примеры

На данной задаче можно отработать технику разбора простых грамматик.

Параллельно-последовательная схема сопротивлений (ПП-схема) это

  • параллельно соединнённые ПП-схемы (записывается как "[s1 s2 .. sk]", k = 1, 2, ... ),
ИЛИ
  • последовательно соединённые ПП-схемы (записывается как "(s1 s2 ... sm)", m = 1, 2, ..),
ИЛИ
  • один резистор (обозначается действительным числом "R").

На рис.1 приведён пример ПП-схемы и её описания в виде скобочной структуры.

Рисунок 1. Пример ПП-схемы и её описания в виде скобочной структуры.

Запишем грамматику описания ПП-схем в нотации Бэкуса — Наура, расширенной регулярными выражениями:

S ::= A | B | number. 
A ::= '(' S+ ')' .
B ::= '[' S+ ']' .
number ::= digit+ ('.' digit+ )? .
digit ::= '0' | '1' | '2' | '3' | '4' |  '5' | '6' | '7' | '8' | '9' .  
  • Вход. Строчка с описанием схемы.

Значения сопротивлений — действительные числа из отрезка [0, 100000]. Размер входа не превосходит 200000 байт.

  • Выход. Значение сопротивления схемы (с точностью до 0.1%).
Вход#1                      Выход#1
[2 2 2]                     0.6666667
Вход#2                      Выход#2
([1 1] 0.5 [3.2 (1 1)])     2.230769
Вход#3                      Выход#3
(3 0 1)                     4
    #include <stdio.h>
    int read_S(double*);
    int read_A(double*);
    int read_B(double*);
    void read_space() {
        int c ;
        do { c = getchar(); } while ( c==' ' || c=='\n' || c=='\t' );
        if( c != EOF ) ungetc(c, stdin); 
    }
    int read_number(double *r) {
        return ( scanf("%lf", r) == 1 );
    }
    int read_A(double *r) {
        int c;
        if( (c=getchar()) == '(') {
            double q;
            *r = 0;
            if( ! read_S(r) ) return 0;
            while( read_S(&q) ) {
                *r += q;
            }
            if( (c=getchar()) == ')') {
                return 1;
            } else {
                return 0;
            }
        } else {
            ungetc(c, stdin);
            return 0;
        }
    }
    int read_B(double *r) {
        int c;
        if( (c=getchar()) == '[' ) {
            double q;
            *r = 0;
            if( ! read_S(r) ) return 0;
            *r = 1 / *r;
            while( read_S(&q) ) {
                if(q != 0) *r += 1 / q;
            }
            *r = 1 / *r;
            if( (c=getchar()) == ']' ) {
                return 1;
            } else {
                return 0;
            }
        } else {
            ungetc(c, stdin);
            return 0;
        }
    }
    int read_S(double *r) {
        read_space();
        return read_A(r) || read_B(r) || read_number(r);
    }
    int main() {
        double r;
        read_S(&r);
        printf("%lf\n", r);
        return 0;
    }

Дятел