/**************************************************\
* Second laborators work at C++                    *
* Stack                                            *
\**************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>

struct stack
  {
  char symbol;
  struct stack *next;
  };

stack *top = NULL, *work;

//////////////////////////////////*\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
void push(char symbol)
  {
  work = (stack *)malloc (sizeof(stack));
  if (work == NULL)
    {
    cout << "Not enough memory to stack...\n";
    exit(1);
    }
  work->symbol = symbol;
  work->next = top;
  top = work;
  }

//////////////////////////////////*\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
char pop()
  {
  if (top->next != NULL)
    {
    work = top;
    top = top->next;
    char tmp;
    tmp = work->symbol;
    free(work);
    return(tmp);
    }
  else
    {
    char tmp;
    tmp = top->symbol;
    free(top);
    top = NULL;
    return(tmp);
    }
  }

//////////////////////////////////*\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
int get_prior(char symbol)
  {
  switch (symbol)
    {
    case '(' : return(0); break;
    case ')' : return(1); break;
    case '=' : return(2); break;
    case '+' : return(3); break;
    case '-' : return(3); break;
    case '*' : return(4); break;
    case '/' : return(4); break;
    case '^' : return(5); break;
     default : return(6);
    }
  }

//////////////////////////////////*\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
//////////////////////////////////*\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
void main()
  {
  char inp_str[256];
  char out_str[256];

  int out = 0;
  int last_prior;

  cout << "als Software /17 sep 1998/ \n";
  cout << "Copyrght by Alex L. Sterinovich\n";
  cout << "We lerning stacks...\n";
  cout << "Enter your string: ";

  cin >> inp_str;
  last_prior = get_prior(inp_str[0]);
  if ((last_prior <= get_prior(inp_str[0])) && (get_prior(inp_str[0]) != 6))
    push(inp_str[0]);
  if (last_prior == 6)
    {
    out_str[out] = inp_str[0];
    out++;
    }

  int i = 1;
  while (inp_str[i] != 0)
    {
    if ((last_prior <= get_prior(inp_str[i])) && (get_prior(inp_str[i]) != 6))
      {
      push(inp_str[i]);
      last_prior = get_prior(inp_str[i]);
      i++;
      }
    else if (get_prior(inp_str[i]) == 6)
           {
           out_str[out] = inp_str[i];
           out++;
           i++;
           }
         else
           {
           while ((last_prior != 0) && (top != NULL))
             {
             out_str[out] = pop();
             if ((out_str[out] == '(') || (out_str[out] == ')'))
               out--;
             last_prior = get_prior(out_str[out]);
             out++;
             }
           last_prior = 0;
           }
    }

  while (top != NULL)
    {
    out_str[out] = pop();
    if ((out_str[out] == '(') || (out_str[out] == ')')) out--;
    out++;
    }
  out_str[out] = 0;
  cout << "\n\n____________\n" << out_str;
  }