infix to postfix v 5.0 (with exponent support), C++ (gcc)

infix to postfix v 5.0 (with exponent support)

#include <iostream>
#include <cmath>
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() {
		if (head == 0) {
			return 0;
		}
		else {
			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 priority(char);
bool isOperator(char);
string toPostfix(string);
int eval(string);

int main() {
	string exp;
	getline(cin, exp);
	cout << toPostfix(exp) << endl;
	cout << eval(toPostfix(exp)) << endl;
    //cout << eval("2 3 2 ^ ^");
	//system("pause");
    return 0;
}

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

bool isOperator(char o) {
	return (o == '+' || o == '-' || o == '*' || o == '/' || o=='^');
}

string toPostfix(string exp) {
	string result = "";
	char d;
	char temp;
	Stack<char> s;
	for (int i = 0; i < exp.length(); i++) {
		d = exp[i];
		if ((d >= '0' && d <= '9') || d == ' ') {
			result += d;
		}
		else if (isOperator(d)) {
			if ((priority(d)>priority(s.Top()) || s.IsEmpty())) {
				s.Push(d);
			}
			else if (priority(d) <= priority(s.Top())) {
                if (d == '^' && s.Top() == '^') {
                    s.Push(d);
                }
                else {
				    while ((priority(d) <= priority(s.Top()) && !s.IsEmpty())) {
					    s.Pop(temp);
					    result += " ";
					    result += temp;
				     }
				s.Push(d);
                }
			}
		}

else if (d == '(') {
			s.Push(d);
		}
		else if (d == ')') {
			while (s.Top() != '(' && !s.IsEmpty()) {
				s.Pop(temp);
				result += " ";
				result += temp;
			}
			s.Pop(temp);
		}
		
	}
	while (!s.IsEmpty()) {
		s.Pop(temp);
		result += " ";
		result += temp;
	}
	return result;
}

int eval(string exp) {
	Stack<int> s;
	char d;
	int m, n;
	for (int i = 0; i < exp.length(); i++) {
		d = exp[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);
		}
        else if (d == '^') {
            s.Pop(m);
            s.Pop(n);
            s.Push(pow(n,m));
        }
	}
	return s.Top();
}


run \| edit \| history \| help	0

λ

                                      .NET NoSQL database for rapid development