Надавите автомата для выявления РНК заколки


Для одного из моих заданий я должен написать спихивать автомата. Он должен был получить строку, которая должна быть проверена, если это шпилька РНК.

Например: gacgcaaguc бы один, поскольку GAC напротив guc, и четыре в середине должны быть либо ВГА Грузии или ААА.

У меня уже есть рабочая программа, которая, однако, при каждом возможном случае. Он имеет 15 if заявления, один для каждого случая, и я уверен, что есть лучший путь.

Теперь я ищу более элегантный способ в C++ для проверки этих случаях:

S -> aW1u | uW1a | gW1c | cW1g
W1-> aW2u | uW2a | gW2c | cW2g
W2-> aW3u | uW3a | gW3c | cW3g
W3-> gW4a
W4->  ca  |  aa

Как вы, наверное, знаете, правая сторона заполняется в стек, и если я попаду в полторы строки, я проверяю, если стек и другая половина моей строки выровнять. Я не понимаю, КПК слишком хорошо, так что, возможно, у вас есть некоторая помощь для парня, который к этому новому.

ГЭС:

#include <stack>

class PDA
{
public:

    enum Language {
      HAIRPIN, // accepts RNA Hairpins
      BRACKETS // Zusatzaufgabe
    };

    enum State {
      IN_PROGRESS = 0, // sequence is valid so far, but not complete
      SUCCESS = 1,     // currently in accepting state, i.e. stack is empty after reading # symbol
      FAIL = 2         // sequence is not in language
    };

    /// Constructor, which specifies which language to check (HAIRPIN by default)
    /// and internally builds up the production rules
    PDA(const Language l = Language::HAIRPIN);

    /// Read the next symbol and internally traverse states
    /// If a fail state was reached in the previous call, the fail state will be maintained
    /// @param a Symbol to read 
    /// @return current state of PDA
    State next(const char a);

    /// Reset the automaton to a state as if newly constructed
    /// I.e. init stack and set state to s0.
    void reset();

protected:
    /// YOUR Member variables and functions

  State transitionfunction(char b, State cur, char stacktop);
  State current;
  std::stack<char> stark;
  int statechange;
};

ЧГК:

#include <stack>
#include "PDA.hpp"
#include <iostream>

using namespace std;


    PDA::PDA(const Language l) {
      current = IN_PROGRESS;
      stark.push('$');
      statechange = 0;
    }

    PDA::State PDA::next(const char a) {
      if (statechange == 1) {
        if (stark.top() == '$') {
          return PDA::SUCCESS;
        }
        else if (stark.top() == a) {
          stark.pop();
          return PDA::IN_PROGRESS;
        }
        else {
          return PDA::FAIL;
        }
      }
      else {
        return transitionfunction(a, current, stark.top());
      }
    }

    void PDA::reset() {
      current = IN_PROGRESS;
      while (!stark.empty()) {
        stark.pop();
      }
      stark.push('$');
      statechange = 0;
    }

    PDA::State PDA::transitionfunction(const char b, PDA::State cur, const char stacktop) {
      if (cur == PDA::FAIL) {
        return PDA::FAIL;
      }

      else if (stacktop =='$') {

        if (b == 'a') {
          stark.push('u');
          stark.push('1');
          return PDA::IN_PROGRESS;
        }
        else if (b == 'c') {
          stark.push('g');
          stark.push('1');
          return PDA::IN_PROGRESS;
        }
        else if (b == 'g') {
          stark.push('c');
          stark.push('1');
          return PDA::IN_PROGRESS;
        }
        else if (b == 'u') {
          stark.push('a');
          stark.push('1');
          return PDA::IN_PROGRESS;
        }
        else {
          return PDA::FAIL;
        }
      }

      else if (stacktop =='1') {

        if (b == 'a') {
          stark.pop();
          stark.push('u');
          stark.push('2');
          return PDA::IN_PROGRESS;
        }
        else if (b == 'c') {
          stark.pop();
          stark.push('g');
          stark.push('2');
          return PDA::IN_PROGRESS;
        }
        else if (b == 'g') {
          stark.pop();
          stark.push('c');
          stark.push('2');
          return PDA::IN_PROGRESS;
        }
        else if (b == 'u') {
          stark.pop();
          stark.push('a');
          stark.push('2');
          return PDA::IN_PROGRESS;
        }
        else {
          return PDA::FAIL;
        }
      }

      else if (stacktop =='2') {

        if (b == 'a') {
          stark.pop();
          stark.push('u');
          stark.push('3');
          return PDA::IN_PROGRESS;
        }
        else if (b == 'c') {
          stark.pop();
          stark.push('g');
          stark.push('3');
          return PDA::IN_PROGRESS;
      }
        else if (b == 'g') {
          stark.pop();
          stark.push('c');
          stark.push('3');
          return PDA::IN_PROGRESS;
      }
        else if (b == 'u') {
          stark.pop();
          stark.push('a');
          stark.push('3');
          return PDA::IN_PROGRESS;
        }

        else {
          return PDA::FAIL;
        }
      }

      else if (stacktop == '3') {
        if(b == 'g'){
          stark.pop();
          stark.push('a');
          stark.push('4');
          return PDA::IN_PROGRESS;
        }

        else {
          return PDA::FAIL;
        }
      }

      else if (stacktop == '4') {
        if(b == 'c'){
          stark.pop();
          stark.push('a');
          statechange = 1;
          return PDA::IN_PROGRESS;
        }
        else if(b == 'a') {
          stark.pop();
          stark.push('a');
          statechange = 1;
          return PDA::IN_PROGRESS;
        }

        else {
          return PDA::FAIL;
        }
      }
    }

Главная:

#include <iostream>
#include "PDA.hpp"

using namespace std;

int main(int argc, char* argv[])
{
    if (argc != 2) {
        cout << "Please only enter one string" << endl;
        return 1;
    }

    string a = argv[1];

    if (a.length() != 10) {
        cout << "The string should have length 10" << endl;
        return 1;
    }

    PDA::State final = PDA::IN_PROGRESS;

    PDA testpin;

    for (uint i = 0; i <= a.length(); i++) {
        final = testpin.next(a[i]);
        if (final == PDA::FAIL) {
            cout << "FAIL" << endl;
            return 1;
        }
        else if (final == PDA::SUCCESS) {
            cout << "ACCEPT" << endl;
            return 0;
        }
    }
}


Комментарии
1 ответ

Я думаю, что ты на правильном пути с КПК! Кажется, как хороший способ подойти к этой проблеме. Я вижу 2 большие проблемы с этим: 1)именования переменных, и 2) большим количеством магических значений. Вот мои мысли.

Именования

В main() например, пользователь вводит string. Я предполагаю, что string предназначена для представления последовательности оснований? Если это так, то должно быть нечто вроде base_sequence.

Аналогично, имена аргументов в функции, как правило, один символ, который передает никакого смысла ни для читателя. В конструкторе PDA, у вас есть аргумент по имени l. Один строчная буква " L " - это действительно плохое имя переменной, потому что он выглядит как номер 1 на первый взгляд. Кого-то, читающего код мог легко перепутать одно другим, так по крайней мере называют это lng или langили, еще лучше, language. (Или, поскольку это фактически не используется нигде и никогда, избавьтесь от нее!)

В next метод PDA принимает один char имени a. Глядя на интерфейс для этого класса, я не знаю, что a представляет. Комментарий говорит symbol to be read. почему не назвать его так? Что-то вроде nextSymbolили nextInputили, еще лучше, next_base поскольку он представляет собой основание с базовой последовательности. Кроме того, имя next передает очень мало. Дальше что? Как насчет nextState() или processNextBase()? И transitionfunction() функция имеет обе эти проблемы. Опять же, b является базовым, так называют это таким образом. Вы обычно не нужно положить слово function в имя функции (если он возвращается указатель на функцию, к примеру).

И почему stack называется stark?

Магические Значения

В transitionfunction()что это значит, что вершина стека содержит символ $? Или 1 или 2или любое другое значение? Вы должны либо сделать именованные константы для них или определение перечислимого типа для них. Вот кстати, кто-то читает ваш код поймет их цель.

Упростить

Я думаю, что ваш transitionfunction() функция может быть упрощена в ряде направлений. Я разорву их в порядке от простых к сложным.

Во-первых, вам не нужен никакой топ-уровня elseС тех пор как только вы входите в одну из них, то функция возвращает. Поэтому структура может быть такой:

if (cur == PDA::FAIL) {
return cur;
}

if (stacktop == '$') {
//... internal "if"s
}

if (stacktop == '1') {
// ... internal "if"s
}
etc.

Далее, возможно, имеет смысл разбить тело на самую верхнюю ifв отдельной функции. Что-то вроде этого:

if (stacktop == '$') {
return handleS(b);
}

if (stacktop == '1') {
return handle1(b);
}

if (stacktop == '2') {
return handle2(b);
}
... etc.

Конечно, я бы назвал обработчики что-то яснее, чем handleX чтобы было понятно, что эти государства представляют.

Затем можно переставить выше в switch оператор как это:

switch (stacktop) {
case '$':
return handleS(b);
break;

case '1':
return handle1(b);
break;

case '2':
return handle2(b);
break;
...etc.
};

Вы можете сделать то же самое в handleX() функции:

switch (b) {
case 'a':
stark.push('u');
stark.push('1');
return PDA::IN_PROGRESS;
break;

case 'c':
//... code for the 'c' base
break;

... etc.
}

Но вы что-то заметили? Каждый случай в handleX() функции будет состоять из 4 операций:


  1. при необходимости поп стека

  2. пуш базы

  3. дополнительно подтолкнуть ряд

  4. дополнительно можно установить состояние изменяется на 1

А потом они возвращаются PDA::IN_PROGRESS. Это выглядит как потенциальный кандидат в табличной дизайн. Можно определить struct что держит эти вещи. Что-то вроде этого:

struct StateChange {
bool popStack;
char base;
char number; // use a better name here
bool setStateChange;
StateChange(bool popIt, char newBase, char newNumber, bool shouldChangeState) : popStack(popIt), base(newBase), number (newNumber), setStateChange(shouldChangeState);
};

Затем вы можете создать std::map из этих. Давайте посмотрим на $ случае:

using StateChangeMap = std::map<char, StateChange>;
StateChangeMap dollarStates;
dollarStates [ 'a' ] = StateChange(false, 'u', '1', false);
dollarStates [ 'c' ] = StateChange(false, 'g', '1', false);
// ... etc. for the rest of the '$' states

Затем вы можете поместить каждый из них в другой map где ключ stacktop значение, которое передается в transitionfunction(). Теперь ваш переходная функция выглядит примерно так:

PDA::State PDA::transitionfunction(const char b, PDA::State cur, const char stacktop) {
if (cur == PDA::FAIL) {
return PDA::FAIL;
}

StateChange nextState = transitionMap [ stacktop ][ b ];
if (nextState.popStack) {
stark.pop();
}
stark.push(nextState.base);
if (nextState.number != '0') { // Here I'm using '0' to represent not pushing a number
stark.push(nextState.number);
}
if (nextState.setStateChange)
{
statechange = 1;
}
return PDA::IN_PROGRESS;
}

Обратите внимание, что вы должны использовать std::map::find() а не operator[] что мне использовать, если вы не санировать ввод, или вам необходимо санировать ввод, так что вы никогда не получите недопустимое значение.

1
ответ дан 2 февраля 2018 в 06:02 Источник Поделиться