我写的程序,不过程序不完整,结构化不好,核心程序和书上的差不多
/*
* 本程序由jiely编写
*
*文件名称：
*摘 要：此程序实现对表达式的求值 包括顺序栈的定义。中缀转后缀，
及后缀表达式求值的算法
*
*作 者： *******
*班 级： *******
*完成日期：
*
*/
#include<iostream.h>
#include<malloc.h>
#include<conio.h>
#include<stdlib.h>
#include<ctype.h>
#include<strstrea.h>
#include<string.h>
#define TRUE 1
#define FALSE -1
#define ERROR 0
#define OVERFLOW -1
#define OK 1
#define NULL 0
#define STACKINCREMENT 10
#define STACK_SIZE 100
typedef int Status;
template<class T>//把STACK定义为模版类
class STACK
{
public:
STACK(int);
~STACK(void);
Status ClearStack(void)const;
int StackEmpty(void)const;
int StackFull(void)const ;
Status Push(const T&);
T Pop(void);
T GetTop(void);
private:
int m_top ;
int m_size ;//栈的大小
T *m_elem ;//存储栈元素
};
template<class T>
STACK<T>::STACK(int size) //初始化构造函数
{
m_size = size;
m_top = -1;
m_elem = new T [m_size];
if(!m_elem)
{
cerr<<"内存分配失败!按任意键退出!"<<endl;
exit(ERROR);
}
}
template<class T> //析够函数
STACK<T>::~STACK(void)
{
delete []m_elem;
}
template<class T>
Status STACK<T>::ClearStack(void)const//清空链栈
{
m_top = -1;
return OK;
}
template<class T>
int STACK<T>::StackEmpty(void)const//判断栈是否为空
{
return (m_top == -1);
}
template<class T>
Status STACK<T>::StackFull(void)const // 判断栈是否为满
{
return (m_top == STACK_SIZE-1);
}
template<class T>
T STACK<T>:: GetTop(void) //得到栈栈顶元素
{
if(StackEmpty())
{
cerr<<"此栈为空栈!无任何元素!"<<endl;
exit(ERROR);
}
else
return m_elem[m_top];
}
template<class T>
Status STACK<T>:: Push(const T&e)//进栈处理
{
if(StackFull())
{
cerr<<"栈满，无法插入元素！"<<endl;
exit(ERROR);
}
else
m_elem[++m_top] = e;
return OK;
}
template<class T>
T STACK<T>::Pop()//出栈处理
{ T e;
if(StackEmpty())
{
cerr<<"栈为空，无元素！"<<endl;
exit(ERROR);
}
else
e = m_elem[m_top--];
return e;
}
/*******************************************
********** 后缀表达式的求值****************/
float Compute(char *str) //str为后缀表达式，定义为float型
{
char ch;
float x;
STACK<float>FloatStack(STACK_SIZE); //将STACK定义为float型
istrstream ins(str); //定义str为字符串输出流对象
for( ins>>ch;ch!='=';ins>>ch) //从ins流中顺序读入一个字符到遇到‘=’号结束
{
switch(ch)
{
case '+':x=FloatStack.Pop()+FloatStack.Pop();break;
case '-':x=FloatStack.Pop(); //出栈的为被减数
x=FloatStack.Pop()-x;break;
case '*':x=FloatStack.Pop()*FloatStack.Pop();break;
case '/':x=FloatStack.Pop();
if(x!=0.0)
{
x=FloatStack.Pop()/x;
} //if
else
{
cerr<<" 被除数不能为0!"<<endl;
exit(ERROR);
} //else
break;
default :
ins.putback(ch);
ins>>x;
break;
} //switch
FloatStack.Push(x);
}
if(!FloatStack.StackEmpty())
{
x=FloatStack.Pop();
if(FloatStack.StackEmpty())
return x;
else
{
cout<<" 表达式输入错误!"<<endl;
exit(ERROR);
} //else
} //if
else
{
cout<<"\n栈为空!!"<<endl;
exit(ERROR);
} //else
} //end
int Precedence(char op) //定义运算符优先级
{
switch(op)
{
case '+':
case '-':
return 1; break;
case '*':
case '/':
//case '%':
return 2; break;
case '(':
case '=':
default:
return 0; break;
}
}
/************************中缀转后缀的算法***********************/
void Change(char *s1,char *s2)//
{
int j=0;
char ch,k;
STACK<char>CharStack(STACK_SIZE); //将STACK定义为char型
istrstream ins(s1); //把s1定义为字符串流形式
CharStack.Push('=');//把'='号入栈
for(ins>>ch; ch!='='; ins>>ch)//依次从字符串流中读入数据直到’=‘时结束
{
if(ch==' ') //为’=‘时，不做任何处理，读入下一个数据
{} //if
else if(ch == '(') //读入的为’（‘时，’（‘入栈
{
CharStack.Push('(');
} //else if
else if(ch == ')') //读入的为’）‘时，处理括号内的数据
{
while(CharStack.GetTop() != '(') //出栈直到栈顶为’（‘为止
s2[j++]=CharStack.Pop();
CharStack.Pop(); //把’（‘删除
} //else if
else if(ch=='+' || ch=='-' || ch=='*' || ch=='/') //读入的为运算符，判断优先级
{
k=CharStack.GetTop();
while(Precedence(k) >= Precedence(ch))
{
s2[j++]=k;
CharStack.Pop();
k=CharStack.GetTop();
} //while
CharStack.Push(ch);
} //else if
else{
if(isdigit(ch) || ch=='.') //函数isdigit判断是否是0~9之间的数字，是的话写入S2中
{
s2[j++]=ch;
} //if
s2[j++]=' '; //S2中输入一个空格
} //else
} //for
ch=CharStack.Pop();
while(ch != '=') //表达式出错的处理
{
if(ch == '(')
{
cout<<"\t表达式输入错误!"<<endl;
exit(ERROR);
} //if
else
{
s2[j++]=ch;
ch=CharStack.Pop();
} //else
} //while
s2[j++]=' ' ;
s2[j++]='=';
s2[j++]='\0';
} //end
/*void compare(char *str)
{
istrstream ins(str);
char ch;
for(ins>>ch;ch!='\0';ins>>ch)
{
if(ch=='+' || ch=='-' || ch=='*' || ch=='/' || isdigit(ch)
||ch!='='||ch=='.')
cerr<<"表达式不是以=号结束，请重新输入！"<<endl;
exit(ERROR);
return OK;
else cerr<<"出现非法字符！"<<endl;
exit(ERROR);
}
}*/
void main()
{
char a[40];
char b[40];
cout<<"请输入一个中缀表达式：(以'='结束)"<<endl;
cin.getline(a,sizeof(a));
//compare(a);
// {
Change(a,b);
// }
cout<<" 其后缀表达式如下 "<<endl;
cout<<b<<endl;
cout<<"求值结果为："<<Compute(b)<<endl;
}
