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

Материал из Викиучебника — открытых книг для открытого мира
Перейти к: навигация, поиск

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


  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

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

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

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

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

PS-sample.png

Рисунок 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;
    }