-
infix to postfix
Hello all. Small logical problem here. I'm doing a program that converts an infix arithmetic expression to a postfix arithmetic expression. The test1 string "a+b*c-d" should output abc*+d- but I can't seem to get it to work. Anyone know what I'm doing wrong?
Thanks
Code:
#include <iostream>
#include <string>
using namespace std;
template<typename object>
class stack{
private:
object *data;
int theSize;
int theCapacity;
//initialize stack
void init(){
theSize = 0;
theCapacity = 1;;
data = new object[theCapacity];
}
//delete entire stack
void emptyStack(){delete[] data;}
public:
//constructor
stack(){init();}
//destrutor
~stack(){emptyStack();}
//copy constructor
stack(const stack& rhs){
init();
*this = rhs;
}
// assignment operator
const stack& operator = (const stack& rhs){
if (this == &rhs) return *this;
emptyStack();
init();
theSize = rhs.theSize;
theCapacity = rhs.theCapacity;
data = new object[rhs.size()];
for (int i = 0; i < rhs.size(); i++)
data[i] = rhs.data[i];
return *this;
}
int size()const{return theSize;}
bool empty() const{return theSize ==0;}
object top() const{
assert(!empty());
return data[theSize - 1];
}
// return data in ith position of stack
object peek(int i) const {
assert( i > 0 && i <= theSize);
return data[theSize - 1];
}
//add to the top of stack
void push(const object& x){
data[theSize++] = x;
if (theSize == theCapacity) {
theCapacity = theCapacity * 2;
object *temp = new object[theCapacity];
for (int i = 0; i < theSize; i++)
temp[i] = data[i];
delete[] data;
data = temp;
}
}
void pop(){
if(empty()) return;
theSize--;
}
void print(){
for (int i = theSize - 1; i >=0; i--)
cout << data[i] << " ";
cout << endl;
}
//print with address
void print_all(){
for ( int i = theSize - 1; i >= 0; i--)
cout << data[i] << " " << " ( " << &data[i] << " ) ";
cout << endl;
}
};
int main()
{
char a = '+';
char b = '-';
char c = '*';
char d = '/';
char e = '(';
char f = ')';
string test1 = ("a+b*c-d");
stack<char> holder;
for (int i = 0; i < test1.size(); i++)
{
if (test1[i] != a && test1[i] != b && test1[i] != c &&
test1[i] != d && test1[i] != e && test1[i] != f)
cout << test1[i];
else if(test1[i] == e)
holder.push(e);
else if(test1[i] == f)
{
while(holder.top() != e)
{
if (holder.top() != e)
{
cout << holder.top();
holder.pop();
}
else
cout << "Error";
}
holder.pop();
}
else if(test1[i] == a || test1[i] == b)
{
while (!holder.empty() && holder.top() != e)
{
if (holder.top() == a || holder.top() == b
|| holder.top() == c || holder.top() == d)
{
cout << holder.top();
holder.pop();
}
}
holder.push(test1[i]);
}
else if(test1[i] == c || test1[i] == d)
{
while (!holder.empty() && holder.top() != e)
{
if (holder.top() == a || holder.top() == b)
{
cout << holder.top();
holder.pop();
}
else break;
}
holder.push(test1[i]);
}
}
while (!holder.empty())
{
cout << holder.top();
holder.pop();
}
system("pause");
return 0;
}
-
Can you isolate which function's messing it up?
-
I don't think you're poping the whole stack. It's better if you give each operator a weight, and then compare the weight. Take a look at pair<char,int> and map<char,int> , that will clean up the logic pretty nicely.