# 逆波兰计算器——完整版C实现

1、什么是逆波兰表达式？

2、逆波兰计算器

(1)、将算数表达式（中缀表达式）转换为逆波兰表达式（后缀表达式）

(2)、用栈实现逆波兰表达式的计算；

3、代码实现

``````//逆波兰计算器
//1、将算数表达式（中缀表达式）转换为逆波兰表达式（后缀表达式）
//规则：从左到右遍历中缀表达式的每个数字和符号，1、若是数字或小数点则直接输出；2、如果是右括号，则出栈输出，一直到左括号结束；3、若是符号，则判断其与栈顶符号的优先级，栈顶符号是右括号或者优先级不高于栈顶符号，
//则栈顶元素依此出栈并输出，直到遇到左括号或栈空才将该符号入栈。如果优先级高于栈顶符号，则直接入栈。
//2、用栈实现逆波兰表达式的计算；

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include
#include
using namespace std;

typedef double ElemType;
typedef char ElemType_c;
#define STACK_INIT_SIZE	10     //栈的总存储容量
#define STACKINCREMENT 10        //增加的容量
#define MAXBUFFER 10           //字符串的长度

typedef struct SqStack//ElemType类型的栈
{
ElemType *base;//栈底指针
ElemType *top;//栈顶指针
int stacksize;//栈总的可用容量
}SqStack;

typedef struct SqStack_c
{
ElemType_c *base;
ElemType_c *top;
int stacksize;
}SqStack_c;

//栈的建立
SqStack* InitStack()
{
SqStack *s = (SqStack *)malloc(sizeof(SqStack));
s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
if (!s->base)
{
exit(0);
}
s->top = s->base;
s->stacksize = STACK_INIT_SIZE;
return s;
}

SqStack_c* InitStack_c()
{
SqStack_c *s = (SqStack_c *)malloc(sizeof(SqStack_c));
s->base = (ElemType_c *)malloc(STACK_INIT_SIZE * sizeof(ElemType_c));
if (!s->base)
{
exit(0);
}
s->top = s->base;
s->stacksize = STACK_INIT_SIZE;
return s;
}

//压栈
bool Push(SqStack *s, ElemType e)
{
if (s->top - s->base >= s->stacksize)
{
s->base = (ElemType *)realloc(s->base, (s->stacksize + STACKINCREMENT) * sizeof(ElemType)); //如果栈满了，扩充栈容量
if (!s->base)
{
return false;
}
s->top = s->base + s->stacksize;
s->stacksize = s->stacksize + STACKINCREMENT;
}
*(s->top) = e;
s->top++;
return true;
}

bool Push_c(SqStack_c *s, ElemType_c e)
{
if (s->top - s->base >= s->stacksize)
{
s->base = (ElemType_c *)realloc(s->base, (s->stacksize + STACKINCREMENT) * sizeof(ElemType_c)); //如果栈满了，扩充栈容量
if (!s->base)
{
return false;
}
s->top = s->base + s->stacksize;
s->stacksize = s->stacksize + STACKINCREMENT;
}
*(s->top) = e;
s->top++;
return true;
}

//出栈
bool Pop(SqStack *s, ElemType &e)
{
if (s->top == s->base)
{
return false;
}
--(s->top);
e = *(s->top);
return true;
}

bool Pop_c(SqStack_c *s, ElemType_c &e)
{
if (s->top == s->base)
{
return false;
}
--(s->top);
e = *(s->top);
return true;
}

//获取栈顶元素，不出栈
ElemType GetTop(SqStack *s)
{
ElemType e;
if (s->top == s->base)
{
exit(0);
}
e = *(s->top - 1);
return e;
}

ElemType_c GetTop_c(SqStack_c *s)
{
ElemType_c e;
if (s->top == s->base)
{
exit(0);
}
e = *(s->top - 1);
return e;
}

//清空栈
void ClearStack(SqStack *s)
{
s->top = s->base;
}

void ClearStack_c(SqStack_c *s)
{
s->top = s->base;
}

//销毁一个栈
void DestroyStack(SqStack *s)
{
int len;
len = s->stacksize;
if (s->base)
{
free(s->base);
}
s->base = s->top = NULL;
s->stacksize = 0;
free(s);
s = NULL;
}

void DestroyStack_c(SqStack_c *s)
{
int len;
len = s->stacksize;
if (s->base)
{
free(s->base);
}
s->base = s->top = NULL;
s->stacksize = 0;
free(s);
s = NULL;
}

//计算栈的当前大小
int StackLen(SqStack *s)
{
return(s->top - s->base);
}

int StackLen_c(SqStack_c *s)
{
return(s->top - s->base);
}

//显示栈内元素
void DisplayStack(SqStack*s)
{
int length;
ElemType *initbase = s->base;
length = (s->top - s->base);
for (int i = 0; i < length; i++)
{
cout << *(s->base) << " ";
s->base++;
}
cout << endl;
s->base = initbase;
}

void DisplayStack_c(SqStack_c* s)
{
int length;
ElemType_c *initbase = s->base;
length = (s->top - s->base);
for (int i = 0; i < length; i++)
{
cout << *(s->base) << " ";
s->base++;
}
cout << endl;
s->base = initbase;
}

int main()
{
//1、将中缀表达式转换为后缀表达式
SqStack_c *C = InitStack_c();
char c, e;
char vect[50];//将输出的后缀表达式存在字符串中，以备计算后缀表达式使用
int j = 0;
printf("请输入算数表达式（中缀表达式），以#作为结束标志 \n");
scanf("%c", &c);
printf("转换的后缀表达式为： \n");
while (c != '#')
{
while (isdigit(c) || c == '.')//如果输入的是数字或者小数点，则直接输出,如果是连续输入的数或小数点，则中间无空格
{
printf("%c", c);
vect[j++] = c;
vect[j] = '\0';
scanf("%c", &c);
if (!(isdigit(c) || c == '.'))
{
printf(" ");
vect[j++] = ' ';
vect[j] = '\0';
}
}

if (c == ')')//如果输入是右括号，则出栈一直到左括号
{
Pop_c(C, e);
while (e != '(')
{
printf("%c ", e);
vect[j++] = e;
vect[j++] = ' ';
vect[j] = '\0';
Pop_c(C, e);
}
}

else if (c == '+' || c == '-')//如果输入是加号或减号，则先判断优先级
{
if (!StackLen_c(C))//如果栈空，则直接入栈
{
Push_c(C, c);
}
else//如果非空，先弹栈
{
do
{
Pop_c(C, e);
if (e == '(')//如果弹出来的是左括号，则直接将c入栈
{
Push_c(C, e);
}
else//如果弹出来的不是左括号，则出栈直到栈空或遇到左括号，再将c入栈
{
printf("%c ", e);
vect[j++] = e;
vect[j++] = ' ';
vect[j] = '\0';
}
} while (e != '(' && StackLen_c(C));
Push_c(C, c);
}
}
else if (c == '*' || c == '/' || c == '(') //如果输入的是乘号或除号或左括号，则直接入栈，因为先算×和先算除都一样
{
Push_c(C, c);
}

else if (c == '#')//如果输入是“#”，结束
{
break;
}
else
{
printf("输入表达式错误，请检查输入 \n");
break;
}
scanf("%c", &c);
}

//最后栈不为空的话，栈中元素全部弹出
while (StackLen_c(C))
{
Pop_c(C, e);
printf("%c ", e);
vect[j++] = e;
vect[j++] = ' ';
vect[j] = '\0';
}
vect[j - 1] = '#';

//2、用栈实现后缀表达式（逆波兰表达式）的计算
SqStack *s = InitStack();//初始化一个栈
double d, f;
char g;
int i = 0;
int k = 0;
char str[MAXBUFFER];
g = vect[k++];

while (g != '#')
{

while (isdigit(g) || g == '.') //判断输入的字符是不是十进制数或小数点
{
//把同一个数存储到一个字符串中
str[i++] = g;
str[i] = '\0';
if (i >= MAXBUFFER)
{
printf("出错：输入的单个数据过大 \n");
return -1;
}
g = vect[k++];

if (g == ' ')//必须在数字后面的空格=才会生效
{
d = atof(str);//字符串转double类型函数
Push(s, d);
i = 0;
break;
}
}
switch (g)
{
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);
Push(s, d / f);
break;
}
g = vect[k++];
}
Pop(s, d);
printf("\n最终结果为：%f\n", d);
system("pause");
return 0;
}
``````