ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 10.03.2026
Просмотров: 103
Скачиваний: 0
if (tmpStr[commaPos + 2] != '=')
throw format_error("Expected '=' sign");
switch (tmpStr[commaPos + 3]){
case 'f':
case 'F':
tmpSw.isTerminalState = true;
break;
case 'q':
case 'Q':
tmpSw.isTerminalState = false;
break;
default:
throw format_error("Next state must begin with 'q' or 'f' letter");
}
stateNumber = tmpStr.substr(commaPos + 4);
tmpSw.nextState = atoi(stateNumber.c_str());
if (tmpSw.nextState == 0 && stateNumber[0] != '0')
throw format_error("State number must contains digits only");
statemachineStates.push_back(tmpSw); // add one switch to array of switches
}
}
class StateMachine: public StateReader{
public:
StateMachine(const char* filename);
bool isDeterministic() const {return deterministic;}
bool hasHangs() const {return hangs;} // means that graph contains isolated node(s)
const StateReader::StatesSwitchArray& GetSwitches() const {return statemachineStates;} // just for printing
bool isExpressionCorrect(const string& expression, int& errorPos);
protected:
void SortStates();
bool _isDeterministic();
bool _hasHangs();
int _findNextIndex(int curState, uchar sym);
private:
bool deterministic;
bool hangs;
};
StateMachine::StateMachine(const char* filename):
StateReader(filename),
deterministic(true),
hangs(false)
{
SortStates();
//some little check of machine
if (statemachineStates.size() == 0)
throw runtime_error("Automat is empty");
if (statemachineStates[0].initialState != 0)
throw runtime_error("There is no initial state");
size_t ln = statemachineStates.size();
bool hasFinalState = false;
for (size_t i = 0; i < ln; i++)
if (hasFinalState = statemachineStates[i].isTerminalState)
break;
if (!hasFinalState)
throw runtime_error("There is no final state");
deterministic = _isDeterministic(); // check if automat is deterministic
hangs = _hasHangs(); // check if may be hangs
}
bool StateMachine::_isDeterministic(){
size_t ln = statemachineStates.size(); // count of elements in array
bool isDet = true;
for (size_t i = 1; i < ln; i++)
if (statemachineStates[i-1].initialState == statemachineStates[i].initialState &&
statemachineStates[i-1].letter == statemachineStates[i].letter &&
(statemachineStates[i-1].isTerminalState != statemachineStates[i].isTerminalState ||
statemachineStates[i-1].nextState != statemachineStates[i].nextState))
{
isDet = false;
break;
};
return isDet;
}
bool StateMachine::_hasHangs(){
size_t ln = statemachineStates.size();
bool isHangs = false;
for (size_t i = 0; i < ln; i++){
if (!statemachineStates[i].isTerminalState){
bool found = false;
// very bad algorithm to search in _SORTED_ array. I was laziness to do better :->
for (size_t j = 0; j < ln; j++){
if (statemachineStates[i].nextState == statemachineStates[j].initialState){
found = true;
break;
}
}
if (!found){
isHangs = true;
break;
}
}
}
return isHangs;
}
void StateMachine::SortStates(){
sort(statemachineStates.begin(), statemachineStates.end()); // common sorting algorithm from <algorithm>
}
int StateMachine::_findNextIndex(int curState, uchar sym){
int found = -1;
size_t ln = statemachineStates.size();
// very bad algorithm to search in _SORTED_ array
for (size_t j = 0; j < ln; j++){
if (statemachineStates[j].initialState == curState &&
statemachineStates[j].letter == sym){
found = j;
break;
}
}
return found;
}
bool StateMachine::isExpressionCorrect(const string& expression, int& errorPos){
if ( !deterministic || hangs)
throw runtime_error("This automat cannot check expression");
// emulate automat's task
int currentState = 0;
size_t strLen = expression.size();
for (int i = 0; i < strLen; i++){
int idx = _findNextIndex(currentState, expression[i]);
if (idx < 0){
errorPos = i;
return false;
}
if (statemachineStates[idx].isTerminalState){
if (i == strLen - 1) return true;
errorPos = i + 1;
return false;
}
currentState = statemachineStates[idx].nextState;
}
errorPos = strLen;
return false;
}
int _tmain(int argc, _TCHAR* argv[]) {
try{ // try to create object of StateMachine
StateMachine sr("states.txt");
StateReader::StatesSwitchArray::const_iterator it; // another way to access to array's elements
for (it = sr.GetSwitches().begin(); it != sr.GetSwitches().end(); it++)
cout << "q" << it->initialState << "," << it->letter << "=" << (it->isTerminalState ? "f" : "q") << it->nextState << endl;
cout << "There are" << (sr.hasHangs() ? "" : "n't") << " hangs" << endl;
cout << "Automat is" << (sr.isDeterministic() ? "" : "n't") << " deterministic" << endl;
string testExpr;
cout << "Please, enter expression to check ";
cin >> testExpr;
// for test with related "states.txt" file
// testExpr = " for( int abAccc= 943 ; a<478; bbc++ )";
// cout << testExpr << endl;
int err;
bool res = sr.isExpressionCorrect(testExpr, err);
if (res) cout << "Expression is correct!" << endl;
else cout << "Incorrect expression. Error position: " << err << endl;
}
catch(const exception& err){
cerr << err.what() << endl;
}
return 0;
}
// Mark for such realization will be 4
Copyright © 2005 – 2010 Voldem@r