STACK ALGORITHMS

(1) reverse array (not in place)
  // arr[] has data, length is max
  // S is initially empty stack
  
  for (i = 0; i < max; i++ )
    S.push (arr[i]);
    
  while ( !S.empty())
    print ( S.pop() );

/****************************************************************************/


(2) Check for palindrome
  // arr[] has string, length is max
  // S is initially empty stack
  
for (i = 0; i < max; i++)
   S.push(arr[i]);
   
for (i = 0; i < max; i++)
   if (arr[i] != S.pop() ) return false;  // not a palindrom
   
return true;                              // is a palindrome

/****************************************************************************/


(3) Evaluate postfix
   // input is postfix expression (no errors)
   // S is initially empty stack
   
while (more input) {
   token = read();
   
   if (token is operand)
      S.push(token);
      
   else if ( token is operator ) {
      S.pop() the required number of operands;
      result = evaluate using operands and token;
      S.push(result);
      }
   }
   
answer is S.peek().

/****************************************************************************/


(4)  Convert infix to postfix. (shunting yard algorithm)
  // Assume operators are left associative.
  // Assume no errors in input expression.
  // S is initially empty stack.
  
while (not done with infix expression) {
   token = read();
   
   if (token is operand) print (token);
   
   else if (token is '(' ) S.push (token);
   
   else if (token is ')' ) {
      S.pop() and print repeatedly until you pop '('   // do not output '('
      }
      
   else if (token is operator)  && ( S.empty()  ||  S.peek() == '(' )
      S.push (token);
      
   else if ( (token is operator) && (precedence(token) > precedence(S.peek()) )
      S.push(token);
      
   else if (token is operator && precedence(token) <= precedence(S.peek()) {
      repeatedly S.pop() and print 
         until ( precedence(S.peek()) < precedence(token) || S.empty() );
      S.push(token);
    
   }      // finished scanning input
   
repeatedly pop and print until S.empty().