Проблема с интерпретацией химических формул, содержащих несколько уровней скобок

Большой проблемой является идея о том, что нам нужно делать все сразу. Пройдите это. Разбить проблему на более простые этапы — это нормально. где каждый шаг лишь приближает вас к желаемому результату.

Рассмотрим проблемный элемент:

    Na(H2(SO3)4)5

Я внесу небольшое изменение (чтобы проиллюстрировать что-то позже):

    S2(H2(SO3)4)5

Словарь и представление данных

_{In the following I will use the term “list“ to refer to whatever structure you use to keep track of parsed (element,count) values. Two good options that come to mind are an array (static will do) or a linked list (singly-linked suffices). Remember, the list must be ordered, you must be able to add an element to it, and index/traverse it.}

^{_{⟶ I used a singly-linked list for my own implementation, but a static array is probably simplest.}}

_{Also, I am not too worried about representing the way the items in the list are stored. I’ll just write, e.g. O2 to represent an element value of "O" and a count value of 2. The way you store the elements is entirely up to you.}

⟶ ^{_{I converted the atomic symbol to it’s corresponding atomic number and stored it as an integer. This is probably overkill for your assignment, but was oh-so-easy and fun, and made dealing with it later so much simpler.}}

Проблема: круглые скобки ⟶ Рекурсивное мышление

Давайте представим, что решаем задачу:

// This is the list of elements we are collecting.
// It is COMMON to all invocations of the function!
// (You could make it a global variable, or just pass a
//  reference to it as argument to your parsing function.)
list = {}

Invoke your parsing function.

[invocation 0]
  "S2 ( H2 ( S O3 ) 4 ) 5"
   ↑ found Sulfur
  list = { S1 }
    Notice how we add BOTH the element AND an automatic count of 1 to the list?
    We can update that count as necessary.

  "S2 ( H2 ( S O3 ) 4 ) 5"
    ↑ found a subscript
      this is where you update the count of the last item in the list
  list = { S2 }

  "S2 ( H2 ( S O3 ) 4 ) 5"
      ↑ found an open parenthesis
        make note of how long your list is
        RECURSE on your parsing function to handle stuff inside
  list = { S2 }
               ↑0

[invocation 1]
  "S2 ( H2 ( S O3 ) 4 ) 5"
        ↑ found Hydrogen
  list = { S2, H1 }
               ↑0

  "S2 ( H2 ( S O3 ) 4 ) 5"
         ↑ found subscript
           update last item
  list = { S2, H2 }
               ↑0

  "S2 ( H2 ( S O3 ) 4 ) 5"
           ↑ found another open parenthesis
             make note of list length and recurse again
  list = { S2, H2 }
               ↑0  ↑1

[invocation 2]
  "S2 ( H2 ( S O3 ) 4 ) 5"
             ↑ found Sulfur
  list = { S2, H2, S1 }
               ↑0  ↑1

  "S2 ( H2 ( S O3 ) 4 ) 5"
              ↑ (no subscript == do nothing)
  list = { S2, H2, S1 }
               ↑0  ↑1

  "S2 ( H2 ( S O3 ) 4 ) 5"
               ↑ found Oxygen
  list = { S2, H2, S1, O1 }
               ↑0  ↑1

  "S2 ( H2 ( S O3 ) 4 ) 5"
                ↑ found subscript
                  update last item
  list = { S2, H2, S1, O3 }
               ↑0  ↑1

  "S2 ( H2 ( S O3 ) 4 ) 5"
                  ↑ found close parenthesis
                    return!
  list = { S2, H2, S1, O3 }
               ↑0  ↑1

[back to invocation 1]
  "S2 ( H2 ( S O3 ) 4 ) 5"
                    ↑ found subscript
                      update all elements STARTING at pre-recursion list length
  list = { S2, H2, S1, O3 }
               ↑0  ↑1
  list = { S2, H2, S1*4, O3 }
               ↑0  ↑1
  list = { S2, H2, S4, O3*4 }
               ↑0      ↑1
  list = { S2, H2, S4, O12 }
               ↑0
                
  "S2 ( H2 ( S O3 ) 4 ) 5"
                      ↑ found close parenthesis
                       return!
  list = { S2, H2, S4, O12 }
               ↑0

[back to invocation 0]
  "S2 ( H2 ( S O3 ) 4 ) 5"
                        ↑ found subscript
                          update all elements starting at pre-recursion list length
  list = { S2, H2, S4, O12 }
               ↑0
  list = { S2, H2*5, S4, O12 }
               ↑0
  list = { S2, H10, S4*5, O12 }
                    ↑0
  list = { S2, H10, S20, O12*5 }
                         ↑0
  list = { S2, H10, S20, O60 }

  "S2 ( H2 ( S O3 ) 4 ) 5"
                         ↑ end of input; all done!
  list = { S2, H10, S20, O60 }

Функцию синтаксического анализа не обязательно писать рекурсивно. Вы могли бы сделать итеративную версию. Для этого требуется дополнительный список для отслеживания длины списка каждый раз, когда обнаруживается открывающая скобка.

Еще один шаг

На этом этапе у вас есть список, который может содержать дубликаты! Примечательно, однако, что мы значительно приблизились к желаемому результату: все скобки удалены!

    S2 H10 S20 O60

Теперь все, что нам нужно сделать, это объединить одинаковые элементы. Есть как минимум два очевидных способа сделать это, оба очень простые. Напишите еще одну функцию для этого.

Основной

Все готово, ваша основная функция должна выглядеть очень просто:

int main()
{
  // s <-- ask user for chemical formula to parse
  char s[1000];
  {
    printf( "formula? " );
    fflush( stdout );
    fgets( s, sizeof(s), stdin );
    char * p = strchr( s, '\n' );
    if (p) *p = '\0';
  }
  
  // here is the list of (element,count) pairs we will parse out of `s`
  #define MAX_LIST_SIZE 1000
  element list[MAX_LIST_SIZE];
  int size = 0;
  
  // first pass (recursive function that does the parentheses)
  parse_elements( s, list, &size, MAX_LIST_SIZE );
  
  // second pass (add duplicate elements)
  simplify_list( list, &size, MAX_LIST_SIZE );
  
  // now we can print out our list
  if (size)
  {
    printf( "%s%d", list[0].element, list[0].count );
    for (int n = 1;  n < size;  n++)
      printf( " + %s%d", list[0].element, list[0].count );
    printf( "\n" );
  }
}

Чтобы решить проблему интерпретации химических формул с вложенными круглыми скобками, я изменил исходный код, чтобы справиться с этой сложностью, используя рекурсивный подход для правильной обработки формул. Ниже приведена модифицированная версия кода, которая дает ожидаемые результаты для примеров типа «Na(H2(SO3)4)5».

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

typedef struct {
    char symbol[3];  // Atom symbol (e.g., "H", "O")
} Atom;

typedef struct {
    char term[50];    // Formula term (e.g., "2H2O", "3CO2")
    char set;         // Unknown associated with the term
} Association;

void processChemicalFormula(char *formula, int coefficient, int table[][50], Atom *atoms, int numAtoms, int termIndex);

void printUnknownsTable(Atom *atoms, int numAtoms, Association *terms, int numTerms) {
    printf("\nAssociation Table between Unknowns and Elements:\n");
    printf("X: ");
    
    // Print header with unknowns
    for (int i = 0; i < numTerms; i++) {
        printf("%c  ", terms[i].set);
    }
    printf("\n");

    // Create and initialize matrix to store quantities associated with each unknown
    int table[numAtoms][50];
    memset(table, 0, sizeof(table));

    // Fill the table with quantities of each atom associated with each unknown
    for (int j = 0; j < numTerms; j++) {
        processChemicalFormula(terms[j].term, 1, table, atoms, numAtoms, j);
    }

    // Print the elements associated with each atom for each unknown
    for (int i = 0; i < numAtoms; i++) {
        printf("%s: ", atoms[i].symbol);
        for (int j = 0; j < numTerms; j++) {
            if (table[i][j] != 0) {
                printf("%d%c  ", table[i][j], terms[j].set);
            } else {
                printf("0%c  ", terms[j].set);
            }
        }
        printf("\n");
    }
}

// Recursive function to process the chemical formula and fill the association table
void processChemicalFormula(char *formula, int coefficient, int table[][50], Atom *atoms, int numAtoms, int termIndex) {
    int len = strlen(formula);
    int i = 0;
    int termCoefficient = 1;  // Initialize term coefficient as 1 by default

    // Check if the first character of the formula is a digit
    if (isdigit(formula[i])) {
        // Use sscanf to read the coefficient from the current position (i)
        sscanf(&formula[i], "%d", &termCoefficient);

        // Update index (i) to move past the read coefficient
        while (isdigit(formula[i]) && i < len) {
            i++;
        }

        // Multiply termCoefficient by the total coefficient of the term
        termCoefficient *= coefficient;
    }

    while (i < len) {
        if (isalpha(formula[i])) {
            // Start of an atom symbol
            char symbol[3] = { formula[i], '\0' };
            i++;

            while (islower(formula[i]) && i < len) {
                strncat(symbol, &formula[i], 1);
                i++;
            }

            // Check if there's a numeric coefficient associated with the atom
            int atomCoefficient = 1;
            if (isdigit(formula[i])) {
                sscanf(&formula[i], "%d", &atomCoefficient);
                while (isdigit(formula[i]) && i < len) {
                    i++;
                }
            }

            // Find the index of the atom in the list of atoms
            int atomIndex = -1;
            for (int k = 0; k < numAtoms; k++) {
                if (strcmp(atoms[k].symbol, symbol) == 0) {
                    atomIndex = k;
                    break;
                }
            }

            // Fill the table with the quantity of atoms associated with the term and unknown
            if (atomIndex != -1) {
                table[atomIndex][termIndex] += coefficient * termCoefficient * atomCoefficient;
            }
        } else if (formula[i] == '(') {
            // Start of a group within parentheses
            int j = i + 1;
            int depth = 1;

            // Find the end of the group within parentheses
            while (j < len && depth > 0) {
                if (formula[j] == '(') {
                    depth++;
                } else if (formula[j] == ')') {
                    depth--;
                }
                j++;
            }

            // Process the coefficient of the group within parentheses, if any
            int groupCoefficient = 1;
            if (j < len && isdigit(formula[j])) {
                sscanf(&formula[j], "%d", &groupCoefficient);
                while (isdigit(formula[j]) && j < len) {
                    j++;
                }
            }

            // Recursively process the group within parentheses
            processChemicalFormula(&formula[i+1], coefficient * termCoefficient * groupCoefficient, table, atoms, numAtoms, termIndex);
            i = j; // Update index to after the processed group
        } else {
            i++;
        }
    }
}

int main() {
    Atom atoms[] = { {"F"}, {"O"}, {"S"}, {"H"}, {"Na"} };
    Association terms[] = { {"2F2(SO4)3", 'A'}, {"Na(H2(SO3)4)5", 'B'} };
    int numAtoms = sizeof(atoms) / sizeof(Atom);
    int numTerms = sizeof(terms) / sizeof(Association);

    printUnknownsTable(atoms, numAtoms, terms, numTerms);

    return 0;
}

Результат:

Association Table between Unknowns and Elements:
Unknown: A  B  
F: 4A  0B  
O: 24A  60B  
S: 6A  20B  
H: 0A  10B  
Na: 0A  1B