infix to postfix v 3.0, C++ (vc++)

infix to postfix v 3.0

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

template<class T>
class Node {
public:
	T data;
	Node<T> *next;

Node() {
		data = 0;
		next = 0;
	}

Node(T value, Node<T> *nxt = 0) {
		data = value;
		next = nxt;
	}
};

template<class T>
class List {
private:
	Node<T> *head, *tail;

public:
	List() {
		head = tail = 0;
	}

int Count() {
		int s = 0;
		Node<T> *temp = head;
		while (temp != 0) {
			temp = temp->next;
			s++;
		}
		return s;
	}

void Add2Head(T value) {
		if (head == 0) {
			head = tail = new Node<T>(value, 0);
		}
		else {
			Node<T> *temp = new Node<T>(value, 0);
			temp->next = head;
			head = temp;
		}
	}

void DeleteHead(T &n) {
		if (head == 0) {
			return;
		}
		else if (head == tail) {
			n = (head->data);
			head = tail = 0;
		}
		else {
			n = (head->data);
			Node<T> *temp = head->next;
			delete head;
			head = temp;
		}
	}

void DeleteHead() {
		if (head == 0) {
			return;
		}
		else if (head == tail) {
			head = tail = 0;
		}
		else {
			Node<T> *temp = head->next;
			delete head;
			head = temp;
		}
	}

T GetHeadValue() {
		return (head->data);
	}

bool IsEmpty() {
		return (head == 0);
	}
    
    void Print() {
        cout << "*****" << endl;
        Node<T> *temp=head;
        while (temp!=0) {
            cout << temp->data << endl;
            temp=temp->next;
        }
        cout << "*****" << endl;
    }
};

template<class T>
class Stack {
private:
	List<T> l;

public:
	void Push(T n) {
		l.Add2Head(n);
	}

bool Pop(T &n) {
		if (l.IsEmpty()) {
			return false;
		}
		else {
			l.DeleteHead(n);
			return true;
		}
	}

bool IsEmpty() {
		return l.IsEmpty();
	}

bool Flush() {
		if (l.IsEmpty()) {
			return false;
		}
		else {
			while (!l.IsEmpty()) {
				l.DeleteHead();
			}
			return true;
		}
	}

T Top() {
		return (l.GetHeadValue());
	}
    
    void Print() {
        l.Print();
    }
};

int getPriority(char o) {
    switch (o) {
        case '*':
        case '/':
        return 2;
        
        case '+':
        case '-':
        return 1;
        
        default:
        return 0;
    }
}

string toPostfix(string exp) {
    string str="";
    char d;
    char temp;
    Stack<char> s;
    for (int i=0;i<exp.length();i++) {
        d=exp[i];
        if (d>='0' && d<='9') {
            str += d;
        }
        else if (d==' ') {
            str += d;
        }
        else if (d=='+' || d=='-' || d=='*' || d=='/') {
            if (s.IsEmpty() || getPriority(d)>getPriority(s.Top())) {
                s.Push(d);
            }
            else if (getPriority(d)<=getPriority(s.Top())) {
                while (getPriority(d)<=getPriority(s.Top()) && !s.IsEmpty()) {
                    s.Pop(temp);
                    str += " ";
                    str += temp;
                }
                s.Push(d);
            }
        }
        else if (d=='(') {
            s.Push(d);
        }
        else if (d==')') {
            while (s.Top()!='(') {
                s.Pop(temp);
                str += " ";
                str += temp;
            }
            s.Pop(temp);
        }
    }
    
    while (!s.IsEmpty()) {
        s.Pop(temp);
        str += " ";
        str += temp;
    }
    return str;
}

int eval(string str) {
    char d;
    int m,n;
    Stack<int> s;
    for (int i=0;i<str.size();i++) {
        d=str[i];
        if (d>='0' && d<='9') {
            s.Push(d-'0');
        }
        else if (d=='+') {
            s.Pop(m);
            s.Pop(n);
            s.Push(m+n);
        }
        else if (d=='-') {
            s.Pop(m);
            s.Pop(n);
            s.Push(n-m);
        }
        else if (d=='*') {
            s.Pop(m);
            s.Pop(n);
            s.Push(m*n);
        }
        else if (d=='/') {
            s.Pop(m);
            s.Pop(n);
            s.Push(n/m);
        }
    }
    return s.Top();
}

void main() {
    /*
	char str[] = "Hello World!";
	Stack s;
	cout << str << endl;
	for (int i = 0; i < sizeof(str); i++) {
		s.Push(str[i]);
	}

cout << endl;
	cout << s.IsEmpty() << endl;
	cout << s.Top() << endl;
    */
	//system("pause");
    cout << toPostfix("((3+2)+(5-1))*4*(9-7)") << endl;
    //cout << eval("5 9 + 4 5 6 + 2 6 * 3 / - * - 4 + 5 2 / -") << endl;
}


run \| edit \| history \| help	0