用栈实现前中后缀表达式转换及求值

本是古典何须时尚 2023-07-17 15:40 7阅读 0赞

前言

1.判断优先级函数

2.运算函数

3.取运算数、操作数进行运算

一、表达式转换

1.中缀表达式转后缀表达式

2.中缀表达式转前缀表达式

二、表达式求值

1.中缀表达式求值

2.后缀表达式求值

3.前缀表达式求值

--------------------

### **前言** ###

**1. ****判断优先级函数**

int getPriority(char op)
    {
        if(op=='+'||op=='-')
            return 0;
        else //'*'或'/'
            return 1;
    }

**2. ****运算函数**

//运算函数
    int calSub(float opand1,char op,float opand2,float &result)
    {
        if(op=='+')
            result=opand1+opand2;
        if(op=='-')
            result=opand1-opand2;
        if(op=='*')
            result=opand1*opand2;
        if(op=='/')
        {
            if(fabs(opand2)<MIN)  //让除数不为0
            {
                // double fabs(double x) 返回 x 的绝对值
                // MIN是一个宏定义，代表非常小的正数
                return 0;
            }
            else   //除数不为0，直接作除法运算
            {
                result=opand1/opand2;
            }
        }
        return 1;
    }

**3. 取运算数、操作数进行运算**

//取运算数、操作数进行运算代码的封装
    int calStackTopTwo(float s1[],int &top1,char s2[],int &top2)
    {
        float opand1,opand2,result;
        char op;
        int flag;
        opand2=s1[top1--]; //先出栈的为第二个操作数
        opand1=s1[top1--]; //后出栈的为第一个操作数
        op=s2[top2--];
        flag=calSub(opand1,op,opand2,result);
        if(flag==0)
        {
            printf("ERROR!");
        }
        s1[++top1]=result;
        return flag;
    }

## 一、表达式转换 ##

**1. 中缀表达式转后缀表达式**

/*
    	中缀表达式转后缀表达式
    	思路：从左往右扫描中缀表达式
    	1）遇到操作数直接写入结果表达式
    	2）遇到左括号直接入栈，遇到右括号就将栈中元素全部出栈直到遇到左括号为止
    	3）遇到一般的运算符：
    	   若该运算符的优先级小于等于栈顶元素的优先级，就将栈顶元素出栈，直到扫描到的运算符的优先级大于栈顶元素的优先级
    */
    void infixToPost(char infix[],char post[],int& postTop)
    {
        //infix[]数组中存放的是中缀表的中缀表达式，post[]中存放的是后缀表达式，postTop存放的是后缀表达式的栈顶指针
        char arr[maxSize];
        int top=-1;//arr[]数组暂存运算符
        int i=0;//设置扫描指针，扫描数组infix[]
        while(infix[i]!='\0')
        {
            if(infix[i]>='a'&&infix[i]<='z') 	//遇到的是操作数，直接入栈
            {
                post[++postTop]=infix[i];
                ++i;
            }
            else if(infix[i]=='(')
            {
                arr[++top]=infix[i];
                ++i;
            }
            else if(infix[i]=='+'||infix[i]=='-'||infix[i]=='*'||infix[i]=='/')
            {
                if(top==-1||arr[top]=='('||getPiority(infix[i])>getPiority(arr[top]))
                    arr[++top]=infix[i++];
                else
                    post[++postTop]=arr[top--];
            }
            else if(infix[i]==')')
            {
                while(arr[top]!='(')
                {
                    post[++postTop]=arr[top--];
                }
                --top;
                ++i;
            }
        }
        while(top!=-1)
        {
            post[++postTop]=arr[top--];
        }
    }

**2. 中缀表达式转前缀表达式**

/*
    	思路：从高后往前扫描中缀表达式
    	1）遇到右括号直接入栈
    	2）遇到操作数直接写进结果表达式
    	3）遇到左括号，就一直出栈，并将出栈元素写进结果表达式
    	4）遇到运算符就进行如下循环：
    		若扫描的运算符优先级小于栈顶元素优先级，就出栈一个元素
    		若扫描的运算符优先级大于等于栈顶元素优先级，就将扫描到的运算符入栈
    */
    void infixToPre(char infix[],int len,char pre[],int& preTop)
    {
        char arr[maxSize];
        int top=-1;
        int i=len-1;
        while(i>=0)
        {
            if(infix[i]>='a'&&infix[i]<='z')
            {
                pre[++preTop]=infix[i];
                --i;
            }
            else if(infix[i]==')')
            {
                arr[++top]=infix[i];
                --i;
            }
            else if(infix[i]=='(')
            {
                while(arr[top]!=')')
                {
                    pre[++preTop]=arr[top--];
                }
                --top;//注意是暂存运算符栈再出栈一个元素将右括号扔掉
                --i;
            }
            else if(infix[i]=='+'||infix[i]=='-'||infix[i]=='*'||infix[i]=='/')
            {
                if(top==-1||arr[top]==')'||getPiority(infix[i])>=getPiority(arr[top]))
                {
                    arr[++top]=infix[i--];
                }
                else
                    pre[++preTop]=arr[top--];
            }
        }
        while(top!=-1)
        {
            pre[++preTop]=arr[top--];
        }
    }

## 二、表达式求值 ##

**1. 中缀表达式求值**

/*
    	思路：从左往右扫描中缀表达式
    	使用两个辅助数组，一个用来存放操作数（栈s1），一个用来存放运算符（栈s2）
    	1）扫描到的是操作数，直接入s1栈
    	2）扫描到的是'('，直接入s2栈
    	3）扫描到的是'+','-','*','/'：则将扫描到的运算符和s2栈顶运算符优先级进行比较，结果如下：
    	扫描到的运算符的优先级大于栈顶运算符优先级，则将运算符入s2栈
    	扫描到的运算的优先级小于等于栈顶运算符优先级，则栈顶出栈一元素，再从操作数栈出栈两元素，先出栈的放在运算符右侧
    	后出栈的放在运算符左侧，将运算结果压入运算数栈，
    	4）扫描到的是')'
    	一直出栈元素，每出栈一个运算符就出栈两个操作数，过程同上，直到遇到一个左括号'('就停止
    	5）当扫描完中缀表达式若栈中还有元素就出栈，每出栈一个运算符就出栈两个元素
    */
    float calInfix(char exp[])
    {
        //定义两个顺序栈
        float s1[maxSize];
        int top1=-1;
        char s2[maxSize];
        int top2=-1;
    
        int i=0;
        while(exp[i]!='\0')   //一直扫描这个表达式串，当遇到串尾(\0)这个字符就结束
        {
            if('0'<=exp[i]&&exp[i]<='9')
            {
                s1[++top1]=exp[i]-'0';
                ++i;
            }
            else if(exp[i]=='(')
            {
                s2[++top2]='(';
                ++i;
            }
            else if(exp[i]=='+'||exp[i]=='-'||exp[i]=='*'||exp[i]=='/')
            {
                //扫描到的运算符的优先级大于栈顶运算符优先级
                if(top2==-1||s2[top2]=='('||getPiority(exp[i])>getPiority(s2[top2]))
                {
                    s2[++top2]=exp[i];
                    ++i;
                }
                //扫描到的运算的优先级小于等于栈顶运算符优先级
                else
                {
                    int flag=calStackTopTwo(s1,top1,s2,top2);
                    if(flag==0)
                        return 0;
                }
            }
            else if(exp[i]==')')  //通过一个循环不停地对运算符栈进行出栈，直到遇到左括号，并对每个出栈的运算符都做一次calStackTopTwo()函数的运算
            {
                while(s2[top2]!='(')
                {
                    int flag=calStackTopTwo(s1,top1,s2,top2);
                    if(flag==0)
                        return 0;
                }
                --top2;
                ++i;
            }
        }
        while(top2!=-1)
        {
            int flag=calStackTopTwo(s1,top1,s2,top2);
            if(flag==0)
                return 0;
        }
        return s1[top1];
    }

**2. 后缀表达式求值**

/*
    	思路：从左往右扫描后缀表达式
    	1）遇到运算数，则入栈
    	2）遇到运算符，则出栈两个元素，先出栈的放在运算符右侧，后出栈的放在运算符左侧，将运算结果压入栈中
    	最终栈中的最后一个元素即为最后需要的数
    */
    float calPostFix(char exp[])
    {
        float stack[maxSize];
        int top=-1;
        int i=0;//i为扫描指针
        while(exp[i]!='\0')
        {
            if(exp[i]>='0'&&exp[i]<='9')
            {
                stack[++top]=exp[i]-'0';
            }
            else if(exp[i]=='+'||exp[i]=='-'||exp[i]=='*'||exp[i]=='/')
            {
                float opand1, opand2, result;
                char op;
                int flag;
    
                opand2=stack[top--];
                opand1=stack[top--];
                op=exp[i];
    
                flag = calSub(opand1,op,opand2,result);
                if(flag == 0)
                {
                    puts(“error”);
                    return 0;
                }
                s[++top]=result;
            }
            ++i;
        }
        return stack[top];
    }

**3. 前缀表达式求值**

/*
    	思路：从右往左扫描前缀表达式
    	1）若遇到操作数，则直接入栈
    	2）若遇到运算符，则出栈两个操作数，先出栈的操作数放在前面，后出栈的操作数放在后面
    	将结果压入栈中，最后栈中剩的那个就是结果
    */
    float calPreFix(char exp[])
    {
        float stack[maxSize];
        int top=-1;
        int i=0;//i为扫描指针
        float result;
        int len=strlen(exp);
        for(i=len-1; i>=0; i--)
        {
            if(exp[i]>='0'&&exp[i]<='9')
            {
                stack[++top]=exp[i]-'0';	//注意字符转数字
            }
            else if(exp[i]=='+'||exp[i]=='-'||exp[i]=='*'||exp[i]=='/')
            {
                float opand1, opand2, result;
                char op;
                int flag;
    
                opand1=stack[top--];
                opand2=stack[top--];
                op=exp[i];
    
                flag = calSub(opand1,op,opand2,result);
                if(flag==0)
                {
                    puts(“error”);
                    return 0;
                }
                stack[++top]=result;
            }
        }
        return stack[top];
    }