#include "iostream.h"

#include "string.h"

#ifndef LL_STACK

#define LL_STACK

#include <list>

using namespace std;

template<class T>
class LLStack
{
private:
list<T> lst;
public:
LLStack(){}

void clear()
{
lst.clear();
}

bool isEmpty () const
{
return lst.empty();
}
//返回最后一个数的数值
T& topEl()
{
return lst.back();
}
//删除最后一个数并返回该数的数值
T pop()
{
T el=lst.back();
lst.pop_back();
return el;
}
//压入一个数
void push(const T& el)
{
lst.push_back(el);
}
};

#endif

char precede(char op1,char op2)//比较运算符的优先级
{
if((op1=='+')||(op1=='-'))
{
if((op2=='+')||(op2=='-')||(op2==')')||(op2=='#'))
return '>';
if((op2=='*')||(op2=='/')||(op2=='('))
return '<';
}

if((op1=='*')||(op1=='/'))
{
if((op2=='+')||(op2=='-')||(op2=='*')||(op2=='/')||(op2=='#')||(op2==')'))
return '>';
if(op2=='(')
return '<';
}

if(op1=='(')
{
if((op2=='*')||(op2=='/')||(op2=='+')||(op2=='-')||(op2=='('))
return '<';
if(op2==')')
return '=';
if(op2=='#')
return ' ';
}

if(op1==')')
{
if((op2=='*')||(op2=='/')||(op2=='+')||(op2=='-')||(op2==')')||(op2=='#'))
return '>';
if(op2=='(')
return ' ';
}

if(op1=='#')
{
if((op2=='*')||(op2=='/')||(op2=='+')||(op2=='-')||(op2=='('))
return '<';
if(op2=='#')
return '=';
if(op2==')')
return ' ';
}

return ' ';
}

int operate(int a,char b,int c)
{
switch(b)
{
case '+':
return a+b;
break;
case '-':
return a-b;
break;
case '*':
return a*b;
break;
case '/':
return a/b;
break;
default:
cout<<"出现错误"<<endl;
return 0;
}
}

void main()
{
LLStack<char> oper;
LLStack<int> numb;
char g[50];
int flag=0;
int a,b;
cout<<"输入计算公式： ";
cin>>g;
int d=strlen(g);
g[d]='#';
g[d+1]='\0';

oper.push('#');

for (int i=0;g[i]!='#'||oper.topEl()!='#';i++)
{
if(g[i]>='0'&&g[i]<='9')
{
a=g[i]-'0';
if(flag==0) numb.push(a);
else numb.push(numb.pop()*10+a);
flag=1;
}
else
{
switch(precede(oper.topEl(),g[i])) {
case '<':
oper.push(g[i]);
break;
case '=':
oper.pop();
break;
case '>':
a=numb.pop();
b=numb.pop();
numb.push(operate(b,oper.pop(),a));
break;
}
flag=0;
}
}
cout<<"the answer is "<<numb.topEl()<<endl;

}

这个程序是用链表实现堆栈，并用堆栈来实现对计算式输入求解
我把头文件的内容也一起放上去，每次不管输入什么都是出错，自己感觉就是执行到oper.push('#');这一句时出错，但又找不出错误。

[此贴子已经被作者于2006-11-12 22:55:21编辑过]

今天这个编了很长时间，结果还是出错，郁闷阿~~
有时候编程序编的不爽，睡觉都睡不踏实啊~~
等那位大哥给我解答，在这里先谢过了阿~

main函数中不清楚你的用意。。。

main函数里是这样的，我先对输入的字符串计算式例如3*（7-2）后面加个#号，然后定义两个堆栈，一个用来存放计算符号，一个用来存放数字，先在那个存放计算符号的堆栈中压入一个#号，然后对字符串进行逐个比较，若是数字直接压入字符栈，若是计算符，用precede函数进行比较，结果是‘<’直接压入栈，是‘=’，则是脱去括号，若是‘>’则调用该符号和最上面的两个数字进行运算，将结果再压入栈。最后的结果就是数字栈中所存的一个数。
这个程序。编译没问题，运行就出错。
自己没有讲清楚，不好意思了。麻烦再看看。

首先oper.push('#');之后,
for (int i=0;g[i]!='#'||oper.topEl()!='#';i++) //但是oper.topEl()=='#';
这个循环就进不去了。



其次，我拿3*（7-2）分析下，错误的地方：
先的优先级一直都是'<'
numb压入3 为3
oper压入* 为#*
oper压入( 为#*(
numb压入7 为37
oper压入- 为#*(-
numb压入2 为372
现在是'>' ,因为precede('-',')')=='>'
numb弹出2，7计算 为3
oper谈出‘-’计算 为#*(
numb压入(7-2) 为35


看出来了吧，多了个(

谢谢阿，找到错误就好，呵呵，自己太不仔细了！自己应该能都调试了！

不过更正一个，
首先oper.push('#');之后,
for (int i=0;g[i]!='#'||oper.topEl()!='#';i++) //但是oper.topEl()=='#';
这个循环就进不去了。


这个进的去的，中间是或运算，0或1的结果是1阿，老大也会有失误的时候啊~~
呵呵，还是万分感谢阿~~

哦，不好意思。谢谢指正