C语言实现逆波兰式转换与求值

核心功能与准备

该程序主要解决两个问题：一是将人类阅读的中缀表达式转换为机器执行的逆波兰式；二是根据转换后的序列进行数学运算。代码未依赖外部复杂库，仅使用标准的 stdio.h 和 string.h，适合在本地环境中编译运行。

主要操作顺序

第1步：初始化栈结构与工具函数

首先定义用于存储字符串的栈结构体 SQ 和存储字符的栈结构体 sq。同时实现基础的辅助函数：

• copystr：手动实现字符串复制，确保数据在不同栈之间转移时不丢失。
• voidSQ/voidsq：初始化栈顶指针为 -1，表示空栈。
• ifempty/ifsqempty：检查栈是否为空，防止越界操作。

第2步：解析输入并生成逆波兰式

主逻辑在 rewrite 函数中。程序遍历用户输入的算式：

1. 处理括号：检测到 ( 时，利用 seek 函数寻找对应的 ) 位置，提取括号内的子表达式递归转换。
2. 处理操作数：非括号字符直接压入临时栈 back。
3. 优先级处理：通过 judge 函数判断符号优先级（乘除为2，加减为3，数字为1）。根据优先级规则调整元素在 front 栈中的排列，完成中缀到后缀的逻辑转换。

第3步：执行数值计算

获取逆波兰式后，调用 calculate 函数：

1. 将后缀表达式的每个字符压入栈 read。
2. 扫描栈顶，当遇到操作符且栈内有两个以上操作数时，调用 execute 进行运算。
3. 计算结果转回 ASCII 码字符，重新压栈等待后续运算。
4. 最终栈底剩余的唯一元素即为算式结果。

第4步：输入输出交互

在 main 函数中，程序提示用户输入算式，自动存储于变量 a，随后依次执行转换与求值，并在控制台打印出逆波兰式形式及最终整型结果。

#include<stdio.h>
#include<string.h>

typedef struct{char s[20][20];int top;}SQ;

void copystr(char *a,char *b)
{
   int i=0;
   do
   {
     b[i]=a[i];
     i++;
   }
   while(a[i]!='\0');
   b[i]='\0';
}

void voidSQ(SQ *s)
{
   s->top=-1;
}

int ifempty(SQ *s)
{
   return(s->top==-1);
}

void push(SQ *S,char *c)
{
   if(S->top==19)
       printf("over flow\n");
   else
   {
     S->top++;
     copystr(c,S->s[S->top]);
   }
}
char *pop(SQ *S)
{
   if(ifempty(S))
   {
     printf("over flow!\n");
     return(NULL);
   }
   else
       return(S->s[S->top--]);
}

int judge(char *c)
{
   if(c[1]=='\0')
       switch(c[0])
   {
       case '+':return(3);
       case '-':return(3);
       case '*':return(2);
       case '/':return(2);
       default:return(1);
   }
   else
       return(1);
}

void write(char *a,char *b,char *c)
{
   strcat(a,c);
   strcat(a,b);
}

int seek(char *c,int start)
{
   int signal=1;
   for(start=start++;c[start]!='\0'&&signal!=0;start++)
   {
       if(c[start]==')')
           signal--;
       else if(c[start]=='(')
           signal++;
   }
   if(signal==0)
       return(start-1);
   else
   {
       printf("输入无效式子\n");
       return(-1);
   }
}
void FB(SQ *A,SQ *B)
{
   for(;!ifempty(A);)
   {
       push(B,A->s[A->top]);
       pop(A);
   }
}

char *rewrite(char *A)
{
   SQ front;
   SQ back;
   int i,j,k,flag=0;
   char *result;
   char mid[20];
   voidSQ(&front);
   voidSQ(&back);
   for(i=0;A[i]!='\0';)
   {
       if(A[i]=='(')
       {
           j=seek(A,i);
           for(k=i+1;k<j;k++)
           {
               mid[k-i-1]=A[k];
           }
           mid[j-i-1]='\0';
           copystr(rewrite(mid),mid);
           push(&back,mid);
           i=j+1;
       }
       else if(A[i]!='(')
       {
           mid[0]=A[i];
           mid[1]='\0';
           push(&back,mid);
           i++;
       }
   }
   FB(&back,&front);
   for(;front.top>=2;)
   {
       flag=0;
       for(i=0;i<=front.top;i++)
       {
           if(judge(front.s[i])==2)
           {
               flag=1;
               break;
           }

       }
       if(flag==1)
       {
           for(;front.top>=2;)
           {
               if(judge(front.s[front.top])==1&&judge(front.s[front.top-1])==2&&judge(front.s[front.top-2])==1)
               {
                   write(front.s[front.top],front.s[front.top-1],front.s[front.top-2]);
                   push(&back,front.s[front.top]);
                    pop(&front);
                   pop(&front);
                    pop(&front);
               }
               else
               {
                   push(&back,front.s[front.top]);
                   pop(&front);
               }
           }
           FB(&front,&back);
           FB(&back,&front);
       }
       else
       {
           for(;front.top>=2;)
           {
               if(judge(front.s[front.top])==1&&judge(front.s[front.top-1])==3&&judge(front.s[front.top-2])==1)
               {
                   write(front.s[front.top],front.s[front.top-1],front.s[front.top-2]);

                   push(&back,front.s[front.top]);
                    pop(&front);
                   pop(&front);
                    pop(&front);
               }
               else
               {
                   push(&back,front.s[front.top]);
                   pop(&front);
               }
           }
           FB(&front,&back);
           FB(&back,&front);
       }
   }
   result=front.s[front.top];
   return(result);
}

typedef struct{char c[20];int top;}sq;
int execute(char a,char b,char c)
{
   switch(a)
   {
   case('+'):return((c-48)+(b-48));
   case('-'):return((c-48)-(b-48));
   case('*'):return((c-48)*(b-48));
   case('/'):return((c-48)/(b-48));
   }
}

void voidsq(sq *s)
{
   s->top=-1;
}

int ifsqempty(sq *s)
{
   return(s->top==-1);
}

void pushsq(sq *s,char x)
{
   if(s->top==19)
       printf("over flow!\n");
   else
   {
       s->top=s->top+1;
       s->c[s->top]=x;
   }
}

void popsq(sq *s)
{
   if(ifsqempty(s))
       printf("over flow!\n");
   else
       s->top--;
}

int just(char c){   
   switch(c)
   {
        case ('+'):return(0);
        case ('-'):return(0);
        case ('*'):return(0);
        case ('/'):return(0);
        default:return(1);
   }
}

void restread(sq *a,sq *b)
{
   for(;!ifsqempty(a);)
   {
        pushsq(b,a->c[a->top]);
        popsq(a);
   }
}


int calculate(char *c)
{
   sq rest,read;
   int i,re;
   voidsq(&rest);
   voidsq(&read);
   for(i=0;c[i]!='\0';i++)
        pushsq(&read,c[i]);
   for(;read.top>=2;)
   {
        for(;read.top>=2;)
        {
            if(just(read.c[read.top])==0&&just(read.c[read.top-1])==1&&just(read.c[read.top-2]) ==1)
            {

                re=execute(read.c[read.top],read.c[read.top-1],read.c[read.top-2]);
                pushsq(&rest,re+48);
                popsq(&read);
                popsq(&read);
                 popsq(&read);
            }
            else
            {
                pushsq(&rest,read.c[read.top]);
                popsq(&read);
            }
        }
        restread(&read,&rest);
        restread(&rest,&read);
   }
   return(read.c[0]-48);
}


void main()
{
   char re[20];
   char a[20];
   printf("请输入算式：\n");
   scanf("%s",a);
   copystr(rewrite(a),re);
   printf("逆波兰式：\n%s\n",re);
   printf("求值结果：\n%d\n",calculate(re));

}

注意事项

由于数组长度限制为20，该程序仅适用于简短的算术表达式。涉及除法时采用整数除法，小数部分会被丢弃。此外，scanf`读取输入时若包含空格可能导致截断，建议输入连续无空格的算式。

以上就是C语言实现逆波兰式转换与求值的详细内容，更多关于C语言数据结构算法的资料请关注本站其它相关文章！