A simple stack application

[hcw88]

Hi all, well. I need to create a push and pop operations using a stack class by using + and - operations.

So far, my coding is:

#include <iostream>
#include <string>
#include <stack>
#include <cctype>   

using namespace std;


void Convert(const string & Infix, string & Postfix);

bool IsOperand(char ch);

bool TakesPrecedence(char OperatorA, char OperatorB);


int main(void)
   {
   char Reply;

   do
      {
      string Infix, Postfix;   

      cout << "Enter an infix expression :"
         << endl;
      cin >> Infix;

      Convert(Infix, Postfix);
      cout << "The equivalent postfix expression is:" << endl
         << Postfix << endl;
      cout << endl << "Do another (y/n)? ";
      cin >> Reply;
      }
   while (tolower(Reply) == 'y');

   return 0;
   }


/* Given:  ch   A character.
   Task:   To determine whether ch represents an operand (here understood
           to be a single letter or digit).
   Return: In the function name: true, if ch is an operand, false otherwise.
*/
bool IsOperand(char ch)
   {
   if (((ch >= 'a') && (ch <= 'z')) ||
      ((ch >= 'A') && (ch <= 'Z')) ||
      ((ch >= '0') && (ch <= '9')))
      return true;
   else
      return false;
   }


/* Given:  OperatorA    A character representing an operator or parenthesis.
           OperatorB    A character representing an operator or parenthesis.
   Task:   To determine whether OperatorA takes precedence over OperatorB.
   Return: In the function name: true, if OperatorA takes precedence over
           OperatorB.
*/
bool TakesPrecedence(char OperatorA, char OperatorB)
   {
   if (OperatorA == '(')
      return false;
   else if (OperatorB == '(')
      return false;
   else if (OperatorB == ')')
      return true;
   else if ((OperatorA == '^') && (OperatorB == '^'))
      return false;
   else if (OperatorA == '^')
      return true;
   else if (OperatorB == '^')
      return false;
   else if ((OperatorA == '*') || (OperatorA == '/'))
      return true;
   else if ((OperatorB == '*') || (OperatorB == '/'))
      return false;
   else
      return true;
      
   }


/* Given:  Infix    A string representing an infix expression (no spaces).
   Task:   To find the postfix equivalent of this expression.
   Return: Postfix  A string holding this postfix equivalent.
*/
void Convert(const string & Infix, string & Postfix)
   {
   stack<char> OperatorStack;
   char TopSymbol, Symbol;
   int k;

   for (k = 0; k < Infix.size(); k++)
      {
      Symbol = Infix[k];
      if (IsOperand(Symbol))
         Postfix = Postfix + Symbol;
      else
         {
         while ((! OperatorStack.empty()) &&
            (TakesPrecedence(OperatorStack.top(), Symbol)))
            {
            TopSymbol = OperatorStack.top();
            OperatorStack.pop();
            Postfix = Postfix + TopSymbol;
            }
         if ((! OperatorStack.empty()) && (Symbol == ')'))
            OperatorStack.pop();   
         else
            OperatorStack.push(Symbol);
         }
      }

   while (! OperatorStack.empty())
      {
      TopSymbol = OperatorStack.top();
      OperatorStack.pop();
      Postfix = Postfix + TopSymbol;
      }
   }

can u guys pls help me. thanks alot

[hcw88]

Given the following expression: 23 + 45 - 25 =

Read an operand(23), push it in stack

Read an operation (+), if this is not an '=' sign, read in another operand (45), push it into stack. Now our stack has

23
45

We then push 2 values out from the stack and add them; the result (68) is then pushed back to the stack.

Read in the next operand (-), which is not an '=' sign, we read in another operand (25) and push it back into the stack, now our stack has

25
68

We then perform a minus operation, the result is 68-25=43, we push this result(23) back into the stack.

Finally we read in the next operator, which is an equal sign, we retrieve from the stack and display it.

So far, my coding is:

#include <iostream>
#include <string>
#include <stack>
#include <cctype> 

using namespace std;


void Convert(const string & Infix, string & Postfix);

bool IsOperand(char ch);

bool TakesPrecedence(char OperatorA, char OperatorB);


int main(void)
{
char Reply;

do
{
string Infix, Postfix; 

cout << "Enter an infix expression :"
<< endl;
cin >> Infix;

Convert(Infix, Postfix);
cout << "The equivalent postfix expression is:" << endl
<< Postfix << endl;
cout << endl << "Do another (y/n)? ";
cin >> Reply;
}
while (tolower(Reply) == 'y');

return 0;
}


/* Given: ch A character.
Task: To determine whether ch represents an operand (here understood
to be a single letter or digit).
Return: In the function name: true, if ch is an operand, false otherwise.
*/
bool IsOperand(char ch)
{
if (((ch >= 'a') && (ch <= 'z')) ||
((ch >= 'A') && (ch <= 'Z')) ||
((ch >= '0') && (ch <= '9')))
return true;
else
return false;
}


/* Given: OperatorA A character representing an operator or parenthesis.
OperatorB A character representing an operator or parenthesis.
Task: To determine whether OperatorA takes precedence over OperatorB.
Return: In the function name: true, if OperatorA takes precedence over
OperatorB.
*/
bool TakesPrecedence(char OperatorA, char OperatorB)
{
if (OperatorA == '(')
return false;
else if (OperatorB == '(')
return false;
else if (OperatorB == ')')
return true;
else if ((OperatorA == '^') && (OperatorB == '^'))
return false;
else if (OperatorA == '^')
return true;
else if (OperatorB == '^')
return false;
else if ((OperatorA == '*') || (OperatorA == '/'))
return true;
else if ((OperatorB == '*') || (OperatorB == '/'))
return false;
else
return true;

}


/* Given: Infix A string representing an infix expression (no spaces).
Task: To find the postfix equivalent of this expression.
Return: Postfix A string holding this postfix equivalent.
*/
void Convert(const string & Infix, string & Postfix)
{
stack<char> OperatorStack;
char TopSymbol, Symbol;
int k;

for (k = 0; k < Infix.size(); k++)
{
Symbol = Infix[k];
if (IsOperand(Symbol))
Postfix = Postfix + Symbol;
else
{
while ((! OperatorStack.empty()) &&
(TakesPrecedence(OperatorStack.top(), Symbol)))
{
TopSymbol = OperatorStack.top();
OperatorStack.pop();
Postfix = Postfix + TopSymbol;
}
if ((! OperatorStack.empty()) && (Symbol == ')'))
OperatorStack.pop(); 
else
OperatorStack.push(Symbol);
}
}

while (! OperatorStack.empty())
{
TopSymbol = OperatorStack.top();
OperatorStack.pop();
Postfix = Postfix + TopSymbol;
}
}

can u guys pls help me. thanks alot

[pseudorandom21]

Post your code inside the code tags (available on most forums):
[code] /* code here */ [/code]

For your "IsOperand" function there are some functions in <cctype> that you may want to look into using, particularly isalpha() and isdigit(). Alternatively you can build an alphabet as a string and use it to test your character against, ex.

const std::string OperandAlphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
char ch = 'a';
return (OperandAlphabet.find(ch) != std::string::npos);

Looking at your approach to most of the functions you've written I think the simple alphabet tip may help you avoid a lot of tedious work.

[pseudorandom21]

Also, just out of the blue--what if you used a C++ Map?

You could store your operator precedence rules as a value in the map:

std::map<char,int> OperatorMap;
OperatorMap.insert( std::pair<char,int>('(',100) );
OperatorMap.insert( std::pair<char,int>(')',100) );

With something like that you could potentially start your operator precedence at 100 and work your way down, and use the operator's mapped value to determine precedence.

if( OperatorMap['('] >= OperatorMap[')'] )
    ;//