C语言实现整数的逆波兰计算器，包括后缀转换和结果计算
本帖最后由 慕容紫小英 于 2020-7-26 23:09 编辑这几天在学习数据结构，网上的代码有大多对基础差的人不太友好，写的比较难懂，我自己也是基础较差，但是我要求自己用自己的方式实现这些经典的程序设计，同时也希望给和我一样跨考计算机的朋友提供一些可供参考的源代码。
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#define maxsize 100
/*本人也是跨考党，已经将代码尽我所能的解释清楚明白，方便于像我一样的初学者观看学习*/
typedef struct SqStack//定义栈
{
char data;
int top;
}SqStack;
int push(SqStack *st,char x)//入栈
{
if((*st).top == maxsize-1)
return 0;
++((*st).top);
(*st).data[(*st).top] = x;
return 1;
}
int pop(SqStack *st,char *x)//出栈
{
if((*st).top == -1)
return 0;
*x = (*st).data[(*st).top];
--((*st).top);
return 1;
}
//中缀表达式转换为逆波兰式
//思路：1.定义两个栈，一个存放数字，称为num栈，一个存放运算符（ + - * / ），称为opera栈
// 2.从左至右逐个遍历字符数组，分为以下两种情况
// 如果是数字直接入栈num
// 如果是运算符：
// （1）opera为空，直接压入
// （2）运算符为左括号'('，直接压入opera
// （3） 运算符为'+' '-' '*' '/' ，则判断当前opera的栈顶元素，并比较优先级
// 一般来说，乘法 = 除法 > 加法 = 减法
// 如果栈顶元素优先级高，则将栈顶元素移出并压入栈num中 ，再将当前运算符压入栈opera中
// 需要注意的是，平级的运算符也是要出栈的
// （4）运算符为右括号')'，连续将opera的栈顶元素压入num中直至碰见左括号'(' ，并将左括号'('移出栈
// 3.读到'\0'之后，将栈opera剩余元素全部压入栈num
void RPN_switch(SqStack *A,SqStack *B,char ss[])
{
int i;
char temp;//记录出栈元素
for(i = 0;i < maxsize;i++)
{
if(ss == '\0')
break;
else
if(isdigit(ss))//数字直接入栈num
{
push(A,ss);
}
else
{
if(isdigit(ss))
{
push(A,' ');//此处的操作是为了分割多位数和个位数，碰见运算符之前如果是数字则将一个' '（空格）压入栈num中
}
switch(ss)//碰见运算符，进行上述判断再压入栈opera
{
case '(':{
push(B,ss);
break;
}
case '+':{
if((*B).top == -1)
{
push(B,ss);
break;
}
else
{
switch((*B).data[(*B).top])
{
case '+':{
pop(B,&temp);
push(A,temp);
push(B,ss);
break;
}
case '-':{
pop(B,&temp);
push(A,temp);
push(B,ss);
break;
}
case '*':{
pop(B,&temp);
push(A,temp);
push(B,ss);
break;
}
case '/':{
pop(B,&temp);
push(A,temp);
push(B,ss);
break;
}
case '(':{
push(B,ss);
break;
}
}
break;
}
}
case '-':{
if((*B).top == -1)
{
push(B,ss);
break;
}
else
{
switch((*B).data[(*B).top])
{
case '+':{
pop(B,&temp);
push(A,temp);
push(B,ss);
break;
}
case '-':{
pop(B,&temp);
push(A,temp);
push(B,ss);
break;
}
case '*':{
pop(B,&temp);
push(A,temp);
push(B,ss);
break;
}
case '/':{
pop(B,&temp);
push(A,temp);
push(B,ss);
break;
}
case '(':{
push(B,ss);
break;
}
}
break;
}
}
case '*':{
if((*B).data[(*B).top]=='/')
{
pop(B,&temp);
push(A,temp);
push(B,ss);
break;
}
else
{
push(B,ss);
break;
}
}
case '/':{
if((*B).data[(*B).top]=='*')
{
pop(B,&temp);
push(A,temp);
push(B,ss);
break;
}
else
{
push(B,ss);
break;
}
}
case ')':{
do
{
pop(B,&temp);
push(A,temp);
}while((*B).data[(*B).top]!='(');
pop(B,&temp);
break;
}
}
}
}
do
{
pop(B,&temp);
push(A,temp);
}while((*B).top > -1);
push(A,'\0');//栈opera元素全部压入栈num之后，栈num最后别忘了补'\0'
strcpy(ss,(*A).data);//用栈num替换原来的字符数组
printf("%s",ss);
}
double Operation(double a,char op,double b)//计算器中的两元操作，由于除法的存在，数据类型选择double
{
if(op == '+')
return a+b;
if(op == '-')
return a-b;
if(op == '*')
return a*b;
if(op == '/')
{
if(b == 0)
{
printf("分母不能为0！\n");
return 0;
}
else
{
return a/b;
}
}
}
void Calculator(char ss[])//计算器的代码部分
{
int i;
double a,b,c;//a,b取出字符数组中的数字，c是两数进行计算之后的结果
double result;//定义一个double类型的栈
int top = -1;
char op;//记录运算符
for(i = 0;i < maxsize;i++)
{
if(ss == '\0')
break;
else
if(isdigit(ss))//此处是将char类型的数字转化为int类型
{
if(isdigit(ss))//碰到数字，判断前一个是否为数字，如果是那么就是多位数
{
result = result*10+(ss-'0');//直接将栈中的数字乘以10加上新读到的数字
}
else//如果前面不是数字就压入新的数字
{
result[++top] = ss-'0';
}
}
else
if(ss=='+'||ss=='-'||ss=='*'||ss=='/')//碰见运算符则应该处理栈顶的两数字了
{
op = ss;
b = result;
a = result;
c = Operation(a,op,b);
result[++top] = c;
}
}
printf(" = %f\n",result);
}
int main(void)
{
printf("欢迎使用逆波兰计算器！\n");
printf("请输入您希望计算的表达式！\n");
char ss;
int i = 0;
fgets(ss,maxsize,stdin);
SqStack num;
SqStack opera;
num.top = -1,opera.top = -1;
RPN_switch(&num,&opera,ss);
Calculator(ss);
return 0;
}
页:
[1]