Генерация постфиксной записи для простых арифметических выражений (алгоритм Дейкстры C++)

Алгоритм перевода в постфиксную запись с помощью стека (алгоритм Дейкстры)

Лексемы выражения, записанного в инфиксной форме, последовательно просматриваются слева направо.

• Если класс очередной лексемы VAR или NUMB, то такая же лексема присваивается к постфиксной записи выражения.
• Если очередная входная лексема является скобкой «(», то она добавляется в верхушку стека.
• Если очередная входная лексема является знаком операции +,-,*,/, то проверяется верхний элемент стека:

а). если верхним в стеке является скобка «(», то входная лексема записывается в стек и читается следующая лексема.

б). если верхним в стеке является знак операции, приоритет которой выше или равен приоритету входной операции, то операция из верхушки стека выталкивается и приписывается к формируемой постфиксной записи (входной символ при этом не изменяется).

• Если очередная входная лексема является закрывающей скобкой «)», то операции из стека последовательно выталкиваются и приписываются к формируемой постфиксной записи до тех пор, пока верхней в стеке не окажется соответствующая открывающая скобка. После этого скобки «взаимно удаляются», т.е. открывающая скобка просто выталкивается из стека и читается следующая входная лексема.

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

Процесс продолжается до исчерпания входного выражения, т.е. до обнаружения лексемы «EndOfL» после обнаружения EndOfL выполняется выталкивание операций из стека и их приписывание (добавление) к выходной постфиксной записи до опустошения стека.

Если в процессе выталкивания операций из стека по EndOfL в верхушке стека обнаруживается открывающая скобка, то выводится сообщение об ошибке (нарушен баланс скобок).

Пример кода:

//---------------------------------------------------------------------------
//процедура перевода строки в Infix
void StrToInfix(char str[nmax], unsigned int Inf[nmax], char VectorP [20][6],char VectorC [20][6],bool *err)
{
int i=0;
int k=0; int kk=0; int m=0;
 while ((str[i]!='\0')&(*err)) //проверяем строку на допустимые символы
 {if ((!isalpha(str[i]))&(!isdigit(str[i]))&(!isdelm(str[i]))&(str[i]!=' '))
 {*err=false;}i++;
 }
 i=0;    //error==true ошибок нет
 while ((str[i]!='\0')&(*err)) //пока не конец строки и нет ошибок
 {
 while (str[i]==' '){i++;}//пропускаем пробелы
 int j=0;
 if (isalpha(str[i])) //if переменная
  {
  j=0;
  while ((isalpha(str[i]))||(isdigit(str[i])))//если обнаружили переменную
  {VectorP[k][j]=str[i];j++; i++;}//пишем её в массив переменных
  Inf[m]=1; Inf[m+1]=k; m++; m++; i--;//добавляем в инфикс коды этой переменной
  VectorP[k][j]='\0'; j++;//дописываем символ конца строки
  k++;//увеличиваем индекс, определяющий в какую строку массива переменных нужно писать п.
  }
  else//если не переменная
  { if (isdigit(str[i]))//если цифра
    {  j=0;
       while (isdigit(str[i]))//пока цифра
       {VectorC[kk][j]=str[i]; i++; j++;}//пишем её в массив чисел
       Inf[m]=2; Inf[m+1]=kk; m++; m++; i--;//добавляем в инфикс коды этого числа
       VectorC[kk][j]='\0'; j++;//дописываем символ конца строки
       kk++;//увеличиваем индекс, определяющий в какую строку массива чисел нужно писать ч.
   }
   else//если не цифра
   {if (isdelm(str[i]))//если разделитель
     {
      if (str[i]=='(') {Inf[m]=40; m++;}//пишем соответствующие коды
      else
      {
      if (str[i]==')') {Inf[m]=41; m++;}
      else
       {
       if (str[i]=='+') {Inf[m]=43; m++;}
       else
        {
        if (str[i]=='-') {Inf[m]=45; m++;} //также можно использовать
        else
         {
         if (str[i]=='*') {Inf[m]=42; m++;}  //switch-case
         else
          {
          if (str[i]=='/') {Inf[m]=47; m++;}
          else
           {
           if (str[i]=='^') {Inf[m]=94; m++;}
           }
          }
         }
        }
       }
      }
     }
   }//если не цифра
  }//если не переменная
  Inf[m]=255;//приписываем крод конца строки
  i++;
 }
}

Содержание архива:

• исходный код  на Borland C++
• пояснительная записка к курсовой работе (18 страниц)