思路:

掌握 运算符高进低出的原则,再结合栈结构存储特点

#include<iostream>
using namespace std;

template<class Type>
struct Node {
	Type data;
	struct Node * next;
};

template<class Type>
class Stack
{
	Node<Type> head;
public:
	Stack();
	void push(Type data);
	void pop();
	Type top();
	bool isEmpty();
	void print();
};

template<class Type>
inline Stack<Type>::Stack()
{
	head.data = '#';
	head.next = NULL;
}

template<class Type>
inline void Stack<Type>::push(Type data)
{
	Node<Type> * tmpNode = new Node<Type>;
	tmpNode->data = data;
	tmpNode->next = head.next;
	head.next = tmpNode;
}

template<class Type>
inline void Stack<Type>::pop()
{
	Node<Type> * tmpNode = head.next;
	head.next = head.next->next;
	delete tmpNode;
}

template<class Type>
inline Type Stack<Type>::top()
{
	return head.next == NULL ? head.data : head.next->data;
}

template<class Type>
inline bool Stack<Type>::isEmpty()
{
	return head.next == NULL;
}

template<class Type>
inline void Stack<Type>::print()
{
	Node<Type> * tmpPtr = head.next;
	while (tmpPtr)
	{
		cout << tmpPtr->data << " ";
		tmpPtr = tmpPtr->next;
	}
	cout << endl << endl ;
}

void infoxsToPostfox(Stack<char> stack, char s[]);
int isp(char );
int icp(char );
bool isDigit(char);
bool isAlpha(char);


int main(void)
{
	Stack<char> stack;
	printf("请输入一个中缀表达式以#结束:\n");
	char str[80];
	gets_s(str);
	infoxsToPostfox(stack,str);
	return 0;
}

void infoxsToPostfox(Stack<char> stack,char s[])
{
	cout << "开始:";
	stack.push('#');
	while (* s != '#')
	{
		if (isDigit(* s) || isAlpha(* s))
		{
			cout << * s << " ";
			s++;
			continue;
		}
		if (* s == ')')
		{
			char ch;
			for (ch = stack.top(),stack.pop(); ch != '(' && ch != '#'; ch = stack.top(),stack.pop())
			{
				cout << ch << " ";
			}
		}
		else 
		{
			char ch;
			for (ch = stack.top(),stack.pop(); icp(* s) <= isp(ch);  ch = stack.top(), stack.pop())
			{
				cout << ch << " ";
			}
			stack.push(ch);
			stack.push(* s);
		}
		s ++;
	}

	while (!stack.isEmpty())
	{
		char ch = stack.top();
		if (ch == '#') {
			return;
		}
		cout << ch << " ";
		stack.pop();
	}
	cout << endl;
}

int isp(char c)
{
	switch (c)
	{
	case '#':
		return 0;
	case '+':
	case '-':
		return 3;
	case '*':
	case '/':
		return 5;
	case '(':
		return 1;
	case ')':
		return 7;
	}
	return -1;
}

int icp(char c)
{
	switch (c)
	{
	case '#':
		return 0;
	case '+':
	case '-':
		return 2;
	case '*':
	case '/':
		return 4;
	case '(':
		return 7;
	case ')':
		return 1;
	}
	return -1;
}

bool isDigit(char c)
{
	return c >= '0' && c <= '9';
}

bool isAlpha(char c) {
	return c >= 'a' && c <= 'z';
}