数据结构之表达式求值(C++版)

#include <windows.h>
#include <iostream>
#include <stdlib.h>
#define MAXBUFFER 10
#define MAXLISTSIZE 100 //预设的存储空间最大容量
using namespace std;

typedef struct{
char *base; //存储空间基址
int *elem;
int top; //栈顶指针
int stacksize; //允许的最大存储空间以元素为单位
}Stack;

void InitStack(Stack &S)
{
// 构造一个最大存储容量为 maxsize 的空栈 S
int maxsize;
maxsize = MAXLISTSIZE;
S.base = new char[maxsize];
S.elem = new int[maxsize];
if (!S.base || !S.elem) exit(1); //存储分配失败
S.stacksize = maxsize;
S.top = 0; //空栈中元素个数为0
}

bool Push(Stack &S, char e)
{
// 若栈的存储空间不满，则插入元素 e 为新的栈顶元素，并返回 TRUE；否则返回 FALSE
if (S.top == S.stacksize) //栈已满，无法进行插入
return FALSE;
S.base[S.top] = e; //插入新的元素
++S.top; //栈顶指针后移
return TRUE;
}

bool Push(Stack &S, int e)
{
// 若栈的存储空间不满，则插入元素 e 为新的栈顶元素，并返回 TRUE；否则返回 FALSE
if (S.top == S.stacksize) //栈已满，无法进行插入
return FALSE;
S.base[S.top] = e; //插入新的元素
++S.top; //栈顶指针后移
return TRUE;
}

bool Pop(Stack &S, char &e)
{
//若栈不空，则删除S的栈顶元素，用 e 返回其值，并返回 TRUE；否则返回 FALSE
if (S.top == 0)
return FALSE;
e = S.base[S.top-1]; //返回非空栈中栈顶元素
--S.top;//栈顶指针前移
return TRUE;
}

bool Pop(Stack &S, int &e)
{
//若栈不空，则删除S的栈顶元素，用 e 返回其值，并返回 TRUE；否则返回 FALSE
if (S.top == 0)
return FALSE;
e = S.base[S.top-1]; //返回非空栈中栈顶元素
--S.top;//栈顶指针前移
return TRUE;
}

int StackLength(Stack S)
{
//返回S的元素个数，即栈的长度。
return S.top;
}
int main()
{
Stack S;
char c, e;
int d, f;
char a[100]; //存储后缀表达式
char str[10]; //临时缓冲区，存储浮点数和多位数
int i = 0, j = 0;
InitStack(S);
cout << "请输入中缀表达式，以#作为结束标志：";
cin >> c;
while(c != '#')
{
while((c >= '0' && c <= '9') || (c == '.'))
{
a[i++] = c;
cin >> c;
if((c < '0' || c > '9') && c != '.')
{
a[i++] = ' ';
}
}
if(')' == c)
{
Pop(S, e);
while('(' != e)
{
a[i++] = e;
a[i++] = ' ';
Pop(S, e);
}
}
else if('+' == c || '-' == c)
{
if(!StackLength(S))
{
Push(S, c);
}
else
{
do
{
Pop(S, e);
if('(' == e)
{
Push(S, e);
}
else
{
a[i++] = e;
a[i++] = ' ';
}
}while(StackLength(S) && '(' != e);
Push(S, c);
}
}
else if('*' == c || '/' == c || '(' == c)
{
Push(S, c);
}
else if('#' == c)
{
break;
}
else
{
cout << "输入格式错误 << endl";
return -1;
}
cin >> c;
}
while(StackLength(S))
{
Pop(S, e);
a[i++] = e;
}
a[i++] = ' ';
a[i++] = '#';
j = i;
cout << "转换的后缀表达式为：";
for(i=0; i<j; i++)
cout << a[i];
cout << endl;
i = 0, j =0;
c = a[i++];
while(c != '#')
{
while((c >= '0' && c <= '9') || c == '.')
{
str[j++] = c;
str[j] = '\0';
if(j >= 10)
{
cout << "出错：输入的数据过大 << endl";
return -1;
}
c = a[i++];
if(c == ' ')
{
d = atof(str);
Push(S, d);
j = 0;
break;
}
}
switch(c)
{
case '+':
Pop(S, f);
Pop(S, d);
Push(S, d+f);
break;
case '-':
Pop(S, f);
Pop(S, d);
Push(S, d-f);
break;
case '*':
Pop(S, f);
Pop(S, d);
Push(S, d*f);
break;
case '/':
Pop(S, f);
Pop(S, d);
if(f != 0)
{
Push(S, d/f);
}
else
{
cout << "错误：除数为0";
return -1;
}
break;
}
c = a[i++];
}
Pop(S, d);
cout << "表达式的结果为：" << d << endl;
}