#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#define maxsize 100
/*本人也是跨考党，已经将代码尽我所能的解释清楚明白，方便于像我一样的初学者观看学习*/
typedef struct SqStack//定义栈
{
char data[maxsize];
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[i] == '\0')
break;
else
if(isdigit(ss[i]))//数字直接入栈num
{
push(A,ss[i]);
}
else
{
if(isdigit(ss[i-1]))
{
push(A,' ');//此处的操作是为了分割多位数和个位数，碰见运算符之前如果是数字则将一个' '（空格）压入栈num中
}
switch(ss[i])//碰见运算符，进行上述判断再压入栈opera
{
case '(':{
push(B,ss[i]);
break;
}
case '+':{
if((*B).top == -1)
{
push(B,ss[i]);
break;
}
else
{
switch((*B).data[(*B).top])
{
case '+':{
pop(B,&temp);
push(A,temp);
push(B,ss[i]);
break;
}
case '-':{
pop(B,&temp);
push(A,temp);
push(B,ss[i]);
break;
}
case '*':{
pop(B,&temp);
push(A,temp);
push(B,ss[i]);
break;
}
case '/':{
pop(B,&temp);
push(A,temp);
push(B,ss[i]);
break;
}
case '(':{
push(B,ss[i]);
break;
}
}
break;
}
}
case '-':{
if((*B).top == -1)
{
push(B,ss[i]);
break;
}
else
{
switch((*B).data[(*B).top])
{
case '+':{
pop(B,&temp);
push(A,temp);
push(B,ss[i]);
break;
}
case '-':{
pop(B,&temp);
push(A,temp);
push(B,ss[i]);
break;
}
case '*':{
pop(B,&temp);
push(A,temp);
push(B,ss[i]);
break;
}
case '/':{
pop(B,&temp);
push(A,temp);
push(B,ss[i]);
break;
}
case '(':{
push(B,ss[i]);
break;
}
}
break;
}
}
case '*':{
if((*B).data[(*B).top]=='/')
{
pop(B,&temp);
push(A,temp);
push(B,ss[i]);
break;
}
else
{
push(B,ss[i]);
break;
}
}
case '/':{
if((*B).data[(*B).top]=='*')
{
pop(B,&temp);
push(A,temp);
push(B,ss[i]);
break;
}
else
{
push(B,ss[i]);
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[maxsize];//定义一个double类型的栈
int top = -1;
char op;//记录运算符
for(i = 0;i < maxsize;i++)
{
if(ss[i] == '\0')
break;
else
if(isdigit(ss[i]))//此处是将char类型的数字转化为int类型
{
if(isdigit(ss[i-1]))//碰到数字，判断前一个是否为数字，如果是那么就是多位数
{
result[top] = result[top]*10+(ss[i]-'0');//直接将栈中的数字乘以10加上新读到的数字
}
else//如果前面不是数字就压入新的数字
{
result[++top] = ss[i]-'0';
}
}
else
if(ss[i]=='+'||ss[i]=='-'||ss[i]=='*'||ss[i]=='/')//碰见运算符则应该处理栈顶的两数字了
{
op = ss[i];
b = result[top--];
a = result[top--];
c = Operation(a,op,b);
result[++top] = c;
}
}
printf(" = %f\n",result[top]);
}
int main(void)
{
printf("欢迎使用逆波兰计算器！\n");
printf("请输入您希望计算的表达式！\n");
char ss[maxsize];
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;
}
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2020-7-26 22:30:10
置顶卡
千斤顶
显身卡