// ННГУ, ВМК, Курс "Методы программирования-2", С++, ООП
//
// Copyright (c) Гергель В.П. 25.07.2002
//
// Перевод арифметических выражений из инфиксной формы в польскую запись 

#include <dos.h>
#include <stdlib.h>
#include <conio.h>
#include <iostream.h>
#include "datlist.h"

class TInfixToPolish {
  protected:
    int GetOperationPrt(char op); // получить приоритет операции
    int IsOperation(char op);     // проверка на знак операции
  public:
    char * ConvertToPolish(char * Exp, int len); // проебразование к польской записи
};

int TInfixToPolish :: GetOperationPrt(char op) { // получить приоритет операции
  int Prt;
  switch ( op ) {
     case '*':
     case '/': Prt = 3; break;
     case '+':
     case '-': Prt = 2; break;
     case '(': Prt = 1; break;
     case '=': Prt = 0; break;
     default:  Prt = -1;
  }
  return Prt;
}

int TInfixToPolish :: IsOperation(char op) { // проверка на знак операции
  if ( op=='+' || op=='-' || op=='*' || op=='/' || op=='=' ) return 1;
  else return 0;
}

// проебразование выражения от инфиксной формы к польской записи
// выражение правильное, без пробелов, заканчивается знаком '='
char * TInfixToPolish :: ConvertToPolish(char * InfixExp, int len) {
  char ch, t, *PolishExp = new char[strlen(InfixExp)+1];
  int  pos = 0; // индекс текущего символа в выражении
  TListStack PolishStack, OperationStack;
  bool key;
  do {
    ch  = InfixExp[pos++];
    if ( isalpha(ch) ) PolishStack.Put(ch); // операнд
    else if ( ch == '(' ) OperationStack.Put(ch);
    else if ( ch == ')' ) {
      while (1) { // перепись операций из стека операций до откр. скобки
        t = OperationStack.Get();
        if ( t == '(' ) break;
        PolishStack.Put(t);
      }
    } else if ( IsOperation(ch) ) { // операции с меньшим приоритетом в стек результатов
        while (! OperationStack.IsEmpty() ) {
          t = OperationStack.Get();
          if ( GetOperationPrt(ch) <= GetOperationPrt(t) ) PolishStack.Put(t);
          else { OperationStack.Put(t); break; }
        }
        OperationStack.Put(ch);
    } // '=' в стеке операций
  } while ( (ch != '=') && (pos < len) );
  pos = 0;  // длина выражения в польской записи
  for ( int i=0; i < len; i++ )
    if ( (InfixExp[i] != '(' ) && (InfixExp[i] != ')' ) ) pos++;
  PolishExp[pos]   = '\0';
  PolishExp[--pos] = '=';
  // извлечение выражения из стека - порядок обратный
  while ( ! PolishStack.IsEmpty() ) PolishExp[--pos] = PolishStack.Get();
  return PolishExp;
}

int main() {
  TInfixToPolish ExpConvertor;
  char Expression[80], *PolishExpression;
  cout << "Перевод арифм. выражения из инфиксной в постфиксную запись" << endl;
  cout << "Введите выражение" << endl;
  cin >> Expression;
  PolishExpression = ExpConvertor.ConvertToPolish(Expression,strlen(Expression));
  cout << "Выражение в инфиксной записи - " << Expression << endl;
  cout << "Выражение в обратной польской записи - " << PolishExpression << endl;
  delete PolishExpression;
  cout << "Нажмите любую клавишу..." << endl;
  getch();
}