C++

Forum

 
infix to postfix

antiflag (9)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
 
StackException.h
#ifndef STACKEXCEPTION_H_INCLUDED
#define STACKEXCEPTION_H_INCLUDED

#include <stdexcept>
#include <string>

using namespace std;

class StackException : public logic_error
{
public:
   StackException(const string& message = "")
      : logic_error(message.c_str())
   {}  // end constructor
}; // end StackException
#endif // STACKEXCEPTION_H_INCLUDED


StackP.h
#ifndef STACKP_H_INCLUDED
#define STACKP_H_INCLUDED

#include "StackException.h"
#include <stack>
typedef char StackItemType;

class Stack
{
public:
// Constructors and destructor:

   Stack();

   Stack(const Stack& aStack);

   ~Stack();

// Stack operations:
   bool isEmpty() const;
   void push(const StackItemType& newItem) throw(StackException);
   void pop() throw(StackException);
   void pop(StackItemType& stackTop) throw(StackException);
   StackItemType getTop(StackItemType& stackTop) const
      throw(StackException);
   StackItemType peek() const;
   //string infixToPostfix(string infixExp);

private:
   struct StackNode
   {
      StackItemType item;
      StackNode    *next;
   }; // end StackNode

   StackNode *topPtr;
   stack<char> opStack;
   stack<int> valStack;
}; // end Stack
// End of header file.

#endif // STACKP_H_INCLUDED


StackP.cpp
#include <cstddef>   // for NULL
#include <new>       // for bad_alloc
#include <string>       // for string
#include <cassert>       // for assert
#include "StackP.h"  // header file

using namespace std;

Stack::Stack() : topPtr(NULL)
{
}  // end default constructor

Stack::Stack(const Stack& aStack)
{
   if (aStack.topPtr == NULL)
      topPtr = NULL;  // original list is empty

   else
   {  // copy first node
      topPtr = new StackNode;
      topPtr->item = aStack.topPtr->item;

      // copy rest of list
      StackNode *newPtr = topPtr;    // new list pointer
      for (StackNode *origPtr = aStack.topPtr->next;
      origPtr != NULL;
      origPtr = origPtr->next)
      {  newPtr->next = new StackNode;
         newPtr = newPtr->next;
    newPtr->item = origPtr->item;
      }  // end for

      newPtr->next = NULL;
   }  // end if
}  // end copy constructor

Stack::~Stack()
{
   // pop until stack is empty
   while (!isEmpty())
      pop();
   // Assertion: topPtr == NULL
}  // end destructor

bool Stack::isEmpty() const
{
   return topPtr == NULL;
}  // end isEmpty

StackItemType Stack :: peek() const
{
    assert(!isEmpty());  // Enforce precondition

	// Stack is not empty; return top
	return topPtr->item;
}

void Stack::push(const StackItemType& newItem)
            throw(StackException)
{
   // create a new node
   try
   {
      StackNode *newPtr = new StackNode;

      // set data portion  of new node
      newPtr->item = newItem;

      // insert the new node
      newPtr->next = topPtr;
      topPtr = newPtr;
   }
   catch (bad_alloc e)
   {
      throw StackException(
    "StackException: push cannot allocate memory.");
   }  // try
}  // end push

void Stack::pop() throw(StackException)
{
   if (isEmpty())
       throw StackException("StackException: stack empty on pop");
   else
   {  // stack is not empty; delete top
      StackNode *temp = topPtr;
      topPtr = topPtr->next;
      // return deleted node to system
      temp->next = NULL;  // safeguard
      delete temp;
   }  // end if
}  // end pop

void Stack::pop(StackItemType& stackTop) throw(StackException)
{
   if (isEmpty())
      throw StackException("StackException: stack empty on pop");
   else
   {  // stack is not empty; retrieve and delete top
      stackTop = topPtr->item;
      StackNode *temp = topPtr;
      topPtr = topPtr->next;

      // return deleted node to system
      temp->next = NULL;  // safeguard
      delete temp;
   }  // end if
}  // end pop

StackItemType Stack::getTop(StackItemType& stackTop) const throw(StackException)
{
   if (isEmpty())
      throw StackException("StackException: stack empty on getTop");
   else
      // stack is not empty; retrieve top
      stackTop = topPtr->item;

    return stackTop;
}  // end getTop
// End of implementation file.


Ok, i have these three files as a framework. I need to use this framework to convert an infix expression to postfix using the following algorithm

for(each character ch in infixExp)
{
switch(ch)
{
case ch is operand, that is, a digit
valStack.push(ch)
break
case ch is a '('
opStack.push(ch)
break
case ch is an operator
if(opStack.isEmpty())
opStack.push(ch)
else if(precedence(ch) > precedence(opStack.peek()))
opStack.push(ch)
else
{
while(!opStack.isEmpty() and precedence(ch) <= precedence(opStack.peek()))
Excute
opStack.push(ch)
}
break
case ch is a ')'
while(opStack.peek() is not a'(')
Execute
opStack.pop()
break
}
}
while(!opStack.isEmpty())
Execute
result = valStack.peek()

Excute means:

operand2 = valStack.peek();
valStack.pop();
operand1 = valStack.peek();
valStack.pop();
op = opStack.peek();
opStack.pop();
result = operand2 op operand1;
valStack.push(result)


Can anyone help me with this. I need this within end of the day.

Thanks in advance.
tcs (519)
But what's your problem? It's nearly everything done.
antiflag (9)
I'm not being able to concatenate the values into a char variable and pass it tinto valStack. I'm not being able to use this part
result = operand2 op operand1;

i.e combine them into a single result.
tcs (519)
Do you have
a) to convert infix to postfix or
b) calculate an infix expression?

May be you've a more detailed look at your job definition. You're right that compressing multiple characters into one isn't the best idea.
antiflag (9)
yup.. i have to convert infix to postfix using the above algorithm and the due date is today. my head is not working right now. can u please help me?
antiflag (9)
#include <iostream>
#include <stack>
#include <cstring>
#include "StackException.h"
#include "StackP.h"
//#include "StackP.cpp"

using namespace std;

string infixToPostfix(string infixExp);
int precedence(char ch);

int main()
{
string infixExp;

cout<<"Enter an infix expression: ";
getline(cin, infixExp);
infixToPostfix(infixExp);

return 0;
}

int precedence(char ch)
{
int temp;
if (ch == '^')
temp = 1;
else if (ch == '*' || ch == '/')
temp = 2;
else if (ch == '+' || ch == '-')
temp = 3;
return temp;

}
string infixToPostfix(string infixExp)
{
Stack opStack;
Stack valStack;
string operand1, operand2, op;
char ch;
char result;
string postfixExp = " ";
int i;

for(int i=0; i < infixExp.length(); i++) // each character ch in the infix expression)
{
ch = infixExp[i];

if(ch == '+' || ch == '-' || ch == '*' || ch == '/')
{
if(opStack.isEmpty())
{
opStack.push(ch);
cout << "Operator" << opStack.peek() << endl;
}
else if(precedence(ch) > precedence(opStack.peek()))
{
opStack.push(ch);
//cout << opStack.getTop(ch) << endl;
}
else
{
while(!opStack.isEmpty() && precedence(ch) <= precedence(opStack.peek()))
{
if(!valStack.isEmpty()){
operand2 = valStack.peek();
valStack.pop();
}
if(!valStack.isEmpty()){
operand1 = valStack.peek();
valStack.pop();
}
op = opStack.peek();
opStack.pop();
postfixExp = operand1 + operand2 + op;
string final[0] = postfixExp[0]+postfixExp[1]+postfixExp[2];
result = final[0];
valStack.push(result);
cout << "RESULT" << valStack.peek();
}
opStack.push(ch);
cout << "Middle operator" << opStack.peek() << endl;
}
}

else if(ch == '(')
{
opStack.push(ch);
}

else if(ch == ')')
{

while(opStack.getTop(ch) != '(')
{
operand2 = valStack.peek();
valStack.pop();
operand1 = valStack.peek();
valStack.pop();
op = opStack.peek();
opStack.pop();
//result = operand1 + op + operand2;
//valStack.push(result);
//opStack.pop();
}
}
else
{
valStack.push(ch);
cout << "DIGIT" << valStack.peek() << endl;
}

}
while(!opStack.isEmpty())
{
if(!valStack.isEmpty()){
operand2 = valStack.peek();
valStack.pop();
}
if(!valStack.isEmpty()){
operand1 = valStack.peek();
valStack.pop();
}
op = opStack.peek();
opStack.pop();
postfixExp = operand1 + operand2 + op;

//for(int i=0;i<postfixExp.length();i++){
//result[i] = postfixExp[i];
//valStack.push(result[i]);
//}
cout<<postfixExp;
// valStack.push(result);
}

//cout << result;
//postfixExp = result;
//cout<<result <<endl;

return postfixExp;
}



this is all i've done..
antiflag (9)
i'm sorry.. but it looks like the program requires to evaluate an infix operation.
tcs (519)
Please, who the hell should read this tohuwabohu? It would really please me if you would format your code in a more readable way. Like this one you've reported above.
tcs (519)
And the next please: Should we guess your problems? It would be nice to be more precisely. Are there any compilation errors? And which one? And if the program runs, what is it's result and does it differ from your expected one? ...
antiflag (9)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
 
#include <iostream>
#include <stack>
#include <cstring>
#include "StackException.h"
#include "StackP.h"

using namespace std;

string infixToPostfix(string infixExp);
int precedence(char ch);

int main()
{
	string infixExp;
	cout<<"Enter an infix expression: ";
	getline(cin, infixExp);
	infixToPostfix(infixExp);
	
	return 0;
}

int precedence(char ch)
{
	int temp;
	if (ch == '^')
	temp = 1;
	else if (ch == '*' || ch == '/')
	temp = 2;
	else if (ch == '+' || ch == '-')
	temp = 3;
	return temp;
}

string infixToPostfix(string infixExp)
{
	Stack opStack;
	Stack valStack;
	string operand1, operand2, op;
	char ch;
	char result;
	string postfixExp = " ";
	int i;
	
	for(int i=0; i < infixExp.length(); i++) // each character ch in the infix expression)
	{
		ch = infixExp[i];
	
		if(ch == '+' || ch == '-' || ch == '*' || ch == '/')
		{
			if(opStack.isEmpty())
			{
				opStack.push(ch);
				cout << "Operator" << opStack.peek() << endl;
			}
			else if(precedence(ch) > precedence(opStack.peek()))
			{
				opStack.push(ch);
			}
			else
			{
				while(!opStack.isEmpty() && precedence(ch) <= precedence(opStack.peek()))
				{
					if(!valStack.isEmpty())
					{
						operand2 = valStack.peek();
						valStack.pop();
					}
					if(!valStack.isEmpty())
					{
						operand1 = valStack.peek();
						valStack.pop();
					}
					op = opStack.peek();
					opStack.pop();
					postfixExp = operand1 + operand2 + op;
					valStack.push(result);
					cout << "RESULT" << valStack.peek();
				} 
			opStack.push(ch);
			cout << "Middle operator" << opStack.peek() << endl; 
			}
		} 
		
		else if(ch == '(')
		{
			opStack.push(ch);
		}
		
		else if(ch == ')')
		{
			while(opStack.getTop(ch) != '(')
			{
				operand2 = valStack.peek();
				valStack.pop();
				operand1 = valStack.peek();
				valStack.pop();
				op = opStack.peek();
				opStack.pop(); 
			} 
		} 
		else 
		{
			valStack.push(ch); 
			cout << "DIGIT" << valStack.peek() << endl; 
		}
		
	}
	while(!opStack.isEmpty())
	{
		if(!valStack.isEmpty())
		{
			operand2 = valStack.peek();
			valStack.pop();
		}
		if(!valStack.isEmpty())
		{
			operand1 = valStack.peek();
			valStack.pop();
		}
		op = opStack.peek();
		opStack.pop(); 
		postfixExp = operand1 + operand2 + op;
	}
	cout << postfixExp;
	return postfixExp;
}



It only works for two operators ie.char . not for the numbers..
Topic archived. No new replies allowed.