Stack operations

[samuelm33]

So I am learning C++ and am working on a couple of challenges. The purpose of the code below is to create a stack, and then use it to convert infix to postfix. Currently anything without parenthesis will be converted no problem, but I cannot get it to work with parenthesis. I am going to post the whole code, but my guess is the problem lies in the toPostFix function, the else if block dealing with the right parenthesis. Thanks a ton for the help I have been smashing my face on the wall for about 4 hours now.

#include <iostream>
#include <string>
#include <sstream>
using namespace std;

struct node { //Stack node
	char ch;
	node *next;
};

void init(node *top) { //Initialize the first node
	top -> next = NULL;
}

bool isEmpty(node *top) { //Check to see if the stack is empty
	if (top->next==NULL) {
		return true;
	} else {
		return false; 
	}
}

void push (node *&top, char c) { //Push the character onto th stack
	node *temp = new node;
	temp->ch = c; 
	temp->next = top;
	top = temp;
}

char pop (node *&top) { //Pop th top node from the stack
	char retval;
	if(isEmpty(top)) {
		cout << "empty" << endl;
		return 0;
	} else {
		node *temp =  top;
		retval = top->ch;
		top = top->next;
		delete temp;
		return retval;
	}
}

char viewTop (node *top) { //View the top of the stack
	char retval;
	if(isEmpty(top)) {
		return 0;
	} else {
		retval = top->ch;
		return retval;
	}
}
 
int priority(char c) { //Check the priority of the character
	int temp = 0;

	if (c == '^')
        temp = 1;
	else  if (c == '*' || c == '/')
        temp = 2;
    else  if (c == '+' || c == '-')
        temp = 3;
    return temp;
}

void toPostFix(node *&top, string infix) //Convrt infix to postfix
{
	stringstream ot;

	for (unsigned i = 0; i < infix.length(); i++) {
		if (infix[i] == '-' || infix[i] == '+' || infix[i] == '*' || infix[i] == '/' || infix[i] == '^') {
			if(isEmpty(top)) {
				push(top,infix[i]);
			}
			else if(priority(infix[i]) < priority(viewTop(top))) {
				push(top,infix[i]);
			} else {
				while(priority(infix[i]) >= priority(viewTop(top)) && !isEmpty(top)) {
					ot << viewTop(top);
					pop(top);
				}
				push(top,infix[i]);
			}

		} else if (infix[i] == ')') {
			while(viewTop(top) != '(' && !isEmpty(top)) {
				ot << viewTop(top);
				pop(top);
			}
		} else if (infix[i] == '(') {
			push(top, infix[i]);
		} else if (infix[i] == ' ') {
			ot << " ";
		} else {
			ot << infix[i];
		}
	}
	while (!isEmpty(top)) {
		ot << viewTop(top);
		pop(top);
	}
		cout << ot.str();
}

void postToInfix()
{

}

int main()
{
	struct node *top = new node;
	string infix;
	char choice;
	char c;
	bool flag = true;

	init(top);

	while (flag) {
		cout << "Choice: ";
		cin >> choice;
		switch(choice) {
		case'1': cout << "operator to push";
				 cin >> c;
				 push(top, c);
				 cout << endl;
				 break;
		case'2': cout << "popping";
				 pop(top);
				 cout << endl;
				 break;
		case'3': cout << "Viewing top";
				 viewTop(top);
				 cout << endl;
				 break;
		case'4': cout << "Enter your expression: ";
				 cin.ignore(256,'\n');
				 getline(cin, infix);
				 toPostFix(top, infix); //a/b-c+d*e-a*c
				 break;
		}
		
	}

	return 0;
}

[ac517]

At line 78 you are popping off the stack and adding to the output until you have an operator on the top with a greater priority than the current infix char. Since you are entering that section when you have a +-*/^ infix char that always have non-zero priority you will always pop off any ('s on the stack since ('s return zero if you call priority() with them.

It is obvious you are trying to code Dijkstra's Shunting-yard algorithm, I believe there may be a deeper problem here. A few days ago I coded the same algorithm and I don't have the code with me, but I don't remember guarding against adding a ( to the output. So I think once you fix that you may have a more subtle bug somewhere. I also had left/right associativity to check in addition to priority which I don't see anywhere here. You should read the Wikipedia article on the Shunting-yard algorithm, they have an example that made coding it quite straightforward. I used the STL <stack> than my own homegrown stack and a map<char,pair<int,int>> to store priority/associativity rather than use a function to return the values.

If you don't have a satisfactory answer by tomorrow I can post my solution when I get to work, its on my work computer.

[ac517]

This will work with all single digit operands 0-9, the operators +-*/^, and will do braces correctly. Gives undefined results for malformed expressions like mismatched brackets, numerous operators in a row, etc. Its basically the most simplistic implementation imaginable. But it display the central idea i was driving at:

#include <algorithm>
#include <iostream>
#include <map>
#include <stack>
#include <string>

using namespace std;

string shuntyard(string exp)
{
   //operator priority and associativity values
   //first is priority, second is associativity
   map<char,pair<int,int> > pri;
   pri['+']=make_pair(2,0);
   pri['-']=make_pair(2,0);
   pri['*']=make_pair(3,0);
   pri['/']=make_pair(3,0);
   pri['^']=make_pair(4,1);
   
   //operator stack
   stack<char> op;
   
   //result output
   string res = "";
   
   for(int i=0;i<exp.size();++i)
   {
      if(exp[i]=='(')
      {
         op.push(exp[i]);
      }
      else if(exp[i]==')')
      {
         while(op.top()!='(')
         {
            res += op.top();
            op.pop();
         }
         op.pop();
      }
      else if(pri.find(exp[i])!=pri.end())
      {
         while(!op.empty() && 
                 (pri[exp[i]].second==0 && pri[op.top()].first==pri[exp[i]].first ||
                  pri[exp[i]].first < pri[op.top()].first))
         {
            res += op.top();
            op.pop();
         }
         op.push(exp[i]);
      }
      else 
      {
         res += exp[i];
      }
   }

   while(!op.empty())
   {
      res += op.top();
      op.pop();
   }

   return res;
}



int main()
{
   string s;
   for(;;)
   {
      cout << "Enter expression or 'q' to quit: ";
      cin >> s;
      if(s=="q") break;
      cout << shuntyard(s) << endl;
   }
   return 0;
}