中缀表达式的计算
利用两个栈来实现，操作数栈，操作符栈
只支持个位数运算
最后必须输入一个'#'
#include<iostream>
using namespace std; template<typename ElementType>
struct Node
{
ElementType data;
Node<ElementType>* next;
}; template<typename ElementType>
class LinkStack
{
public:
LinkStack()
{
top = new Node<ElementType>;
top = NULL;
}
~LinkStack()
{
delete top;
}
void push(ElementType item);
void pop();
ElementType front() const;
private:
Node<ElementType>*top;
}; template<typename ElementType>
void LinkStack<ElementType>::push(ElementType item)
{
Node<ElementType>*p = new Node<ElementType>;
p->data = item;
p->next = top;
top = p;
} template<typename ElementType>
void LinkStack<ElementType>::pop()
{
Node<ElementType>*p = top;
top = top->next;
delete p;
} template<typename ElementType>
ElementType LinkStack<ElementType>::front()const
{
return top->data;
} bool isNum(char c)
{
return (c <= '9' && c >= '0');
} char Precede(char f, char c)
{
if (f == '+')
{
if (c == '*' || c == '/' || c == '(')return '<';
else return '>';
}
else if (f == '-')
{
if (c == '*' || c == '/' || c == '(')return '<';
else return '>';
}
else if (f == '*')
{
if (c == '(')return '<';
else return'>';
}
else if (f == '/')
{
if (c == '(')return '<';
else return'>';
}
else if (f == '(')
{
if (c == ')')return '=';
else return '<';
}
else if (f == ')')return '>';
else if (f == '#')
{
if (c == '#')return '=';
else return '<';
}
} int Operator(int a, int b, LinkStack<char>* L)
{
if (L->front() == '+')
return a + b;
else if (L->front()== '-')
return a - b;
else if (L->front() == '*')
return a*b;
else if (L->front() == '/')
return a / b;
} void evaluate(LinkStack<char>*SOPTR, LinkStack<int>*SOPND)
{
SOPTR->push('#');
char c;
cin >> c;
while (c != '#' || SOPTR->front() != '#')
{
if (isNum(c))
{
int n = c - '0';
SOPND->push(n);
cin >> c;
}
else
{
switch (Precede(SOPTR->front(), c))
{
case '<':SOPTR->push(c);
cin>>c;
break;
case '=':SOPTR->pop();
cin >> c;
break;
case '>':
int a = SOPND->front();
SOPND->pop();
int b = SOPND->front();
SOPND->pop();
SOPND->push(Operator(a, b, SOPTR));
SOPTR->pop();
}
}
}
cout << SOPND->front() << endl;
delete SOPND, SOPTR;
} int main()
{
cout << "input the infix expression:(you must input # to stop input)" << endl;
LinkStack<char>* SOPTR = new LinkStack<char>;
LinkStack<int>* SOPND = new LinkStack<int>;
evaluate(SOPTR,SOPND); return 0;
}