精华内容
下载资源
问答
  • 中缀表达式计算

    2018-04-24 11:15:28
    c++课程设计,实现中缀表达式计算可以完成转换成中缀表达式计算结果
  • C语言 : 中缀表达式 计算求值、后缀表达式 计算求值、中缀表达式 转 后缀表达式

    代码来源 :
    bilibili网站 :https://www.bilibili.com/video/av91996256?from=search&seid=17449723308302029804

    注意:中缀表达式 转 后缀表达式,函数 有误。

    中缀表达式 计算过程 :
    在这里插入图片描述

    后缀表达式 计算过程 :
    在这里插入图片描述

    中缀表达式 转 后缀表达式 :
    在这里插入图片描述

    /* 前缀:prefix
    ** 中缀:Infix
    ** 后缀:Suffix
    exit为C++的退出函数,声明于stdlib.h中,对于C++其标准的头文件为cstdlib,
    声明为 void exit(int value);
    exit的功能为,退出当前运行的程序,并将参数value返回给主调进程。
    在main中return v;的效果 与exit(v);相同。
    exit(1)和exit(-1)是分别返回1和-1到主调程序。
    exit(0): 返回0,表示程序正常退出,非0表示非正常退出。
    exit(1):表示异常退出。
    */
    
    #include <stdio.h>
    #include <stdlib.h>
    // #include <cstring>
    #include <string.h>
    
    enum boolean
    {
        FALSE,
        TRUE
    };
    
    typedef enum boolean Bool; //枚举方式进行重定义
    typedef int ElementType;
    
    struct stack
    {
        ElementType *element;
        int MaxSize; //大小
        int top;     //线性表:长度; 栈:栈顶指针
    };
    
    typedef struct stack Stack;
    
    //需要的函数
    void InitStack(Stack *S, int sz);   //初始化函数
    void FreeStack(Stack *S);           //释放栈空间(即: 空间无)
    Bool Push(Stack *S, ElementType X); //压栈
    ElementType Pop(Stack *S);          //弹栈(栈顶弹出)
    ElementType GetTop(Stack *S);       // 获取栈顶元素
    void MakeStackEmpty(Stack *S);      //置空(无元素,空间依然存在)
    Bool IsStackEmpty(Stack *S);        //栈是否为空
    Bool IsStackFull(Stack *S);         //栈是否为满
    
    void EvaluteMidPostfix();  //中缀表达式求值
    void EvaluteBackPostfix(); //后缀表达式求值
    void MidToBack();          //中缀转后缀
    
    int main()
    {
        //printf("%d\n", (int)('9' - 48));
    
        //EvaluteMidPostfix();
        EvaluteBackPostfix();
        //MidToBack();
        return 0;
    }
    
    //实现各个功能函数
    
    void InitStack(Stack *S, int sz) //初始化栈(栈为空)
    {
        S->MaxSize = sz;
        S->top = -1; //指向-1; 一个元素:指向0
        S->element = (ElementType *)malloc(sizeof(ElementType) * S->MaxSize);
    }
    
    void FreeStack(Stack *S) //释放栈空间(即: 空间无)
    {
        free(S->element); //释放元素
    }
    
    Bool IsStackFull(Stack *S) //栈是否为满
    {
        // return S->top == S->MaxSize-1;
        if (S->top == S->MaxSize - 1)
            return TRUE;
        return FALSE;
    }
    
    Bool IsStackEmpty(Stack *S) //栈是否为空
    {
        //return S->top == -1;
        if (S->top == -1)
            return TRUE;
        return FALSE;
    }
    
    Bool Push(Stack *S, ElementType x) //压栈
    {
        //先判断 栈满?
        if (IsStackFull(S))
            return FALSE;
        else
        {
            //指针指向新的栈顶
            S->element[++S->top] = x; //top先加一
            return TRUE;
        }
    }
    
    ElementType Pop(Stack *S) //弹栈(栈顶弹出)
    {
        if (IsStackEmpty(S))
        {
            //return FALSE;
            exit(1); //表示异常退出
        }
        else
        {
            //先弹出元素,指针下移
            return S->element[S->top--];
        }
    }
    
    ElementType GetTop(Stack *S) // 获取栈顶元素
    {
        if (IsStackEmpty(S))
        {
            //return FALSE;
            exit(1); //表示异常退出
        }
        else
        {
            //先弹出元素,指针下移
            return S->element[S->top];
        }
    }
    
    void MakeStackEmpty(Stack *S) //置空(无元素,空间依然存在)
    {
        S->top = -1;
    }
    
    //从操作数栈取两个操作数;从操作符栈取一个操作符
    //用操作符对操作数进行运算。将计算结果压入操作数栈。
    void compute(Stack *Sptr, Stack *Spnd) //定义计算过程
    {
        int k;
        switch (Pop(Sptr))
        {
        case '+':
            k = Pop(Spnd) + Pop(Spnd);
            break;
        case '-':
            k = Pop(Spnd);
            k = Pop(Spnd) - k;
            break;
        case '*':
            k = Pop(Spnd) * Pop(Spnd);
            break;
        case '/':
            k = Pop(Spnd);
            k = Pop(Spnd) / k;
            break;
        }
        Push(Spnd, k); //将计算结果压入操作数栈。
    }
    
    void EvaluteMidPostfix() //中缀表达式计算求值
    {
        char buf[80];
        printf("Please input Infix : \n");
        scanf("%s", buf);
    
        //strcpy_s(buf, 80, "8-(3+5-4/2)*2/3");
    
        Stack *Spnd = (Stack *)malloc(sizeof(Stack));
        Stack *Sptr = (Stack *)malloc(sizeof(Stack));
    
        InitStack(Spnd, 80);
        InitStack(Sptr, 80);
    
        int i = 0;
        while (buf[i] != '\0')
        {
            //操作数类型
            if (buf[i] >= '0' && buf[i] <= '9')
                Push(Spnd, (int)(buf[i] - 48)); //printf("%d",(int)('9'-48));
            //操作符类型
            //优先级最高(若无括号&&之后也是*或/,从左到右计算)
            else if (buf[i] == '*' || buf[i] == '/') 
            {
                // if(Sptr->top == -1 || GetTop(Sptr)=='(')//操作符直接入栈的条件
                //     Push(Sptr,buf[i]);
                if (GetTop(Sptr) == '*' || GetTop(Sptr) == '/')
                {
                    compute(Sptr, Spnd);
                }
                Push(Sptr, buf[i]);
            }
            else if (buf[i] == '+' || buf[i] == '-')
            {
                while (Sptr->top != -1 && GetTop(Sptr) != '(') //判断语句不可交换位置。
                {
                    compute(Sptr, Spnd);
                }
                Push(Sptr, buf[i]);
            }
            else if (buf[i] == ')')
            {
                while (GetTop(Sptr) != '(')
                {
                    compute(Sptr, Spnd);
                }
                Pop(Sptr);
            }
            else if (buf[i] == '(')
            {
                Push(Sptr, buf[i]);
            }
            i++;
        }
        while (Sptr->top != -1) //结束条件: 操作符栈为空
            compute(Sptr, Spnd);
        printf("%d", Pop(Spnd));
    }
    
    void EvaluteBackPostfix() //后缀表达式计算求值
    {
        char buf[80];
        printf("Please input Suffix : \n");
        scanf("%s", buf);
        Stack *Spnd = (Stack *)malloc(sizeof(Stack));
        InitStack(Spnd, 80);
    
        int i = 0, k;
        while (buf[i] != '\0')
        {
            switch (buf[i])
            {
            case '+':
                k = Pop(Spnd) + Pop(Spnd);
                Push(Spnd, k);
                break;
            case '-':
                k = Pop(Spnd);
                k = Pop(Spnd) - k;
                Push(Spnd, k);
                break;
            case '*':
                k = Pop(Spnd) * Pop(Spnd);
                Push(Spnd, k);
                break;
            case '/':
                k = Pop(Spnd);
                k = Pop(Spnd) / k;
                Push(Spnd, k);
                break;
            default:
                Push(Spnd, (int)(buf[i] - 48));
            }
            i++;
        }
        printf("%d", Pop(Spnd));
    }
    
    void MidToBack() //中缀转后缀
    {
        char buf[80];
        printf("Infix to suffix : \n");
        scanf("%s", buf); // 读入中缀表达式
    
        //strcpy_s(buf, 80, "8-(3+5-4/2)*2/3");
    
        Stack *Sptr = (Stack *)malloc(sizeof(Stack));
    
        InitStack(Sptr, 80);
    
        int i = 0;
        while (buf[i] != '\0')
        {
            //操作数类型
            if (buf[i] >= '0' && buf[i] <= '9')
                printf("%c", buf[i]);
            //操作符类型
            else if (buf[i] == '*' || buf[i] == '/')
            {
                if (IsStackEmpty(Sptr))
                {
                    Push(Sptr, buf[i]); //栈空,往里放东西
                }
                else if (GetTop(Sptr) == '*' || GetTop(Sptr) == '/')
                {
                    printf("%c", Pop(Sptr));
                    Push(Sptr, buf[i]);
                }
                else
                {
                    Push(Sptr, buf[i]);
                }
            }
            else if (buf[i] == '+' || buf[i] == '-')
            {
                if (IsStackEmpty(Sptr))
                {
                    Push(Sptr, buf[i]); //栈空,往里放东西
                }
            }
            else if (buf[i] == ')')
            {
                while (GetTop(Sptr) != '(')
                {
                    printf("%c", Pop(Sptr));
                }
                Pop(Sptr);
            }
            else if (buf[i] == '(')
            {
                Push(Sptr, buf[i]);
            }
            i++;
        }
        while (Sptr->top != -1) //结束条件: 操作符栈为空
            printf("%c", Pop(Sptr));
    }
    
    // 中缀:8-(3+5-4/2)*2/3 : 4
    // 中缀:7+2*3/(2-3) : 1
    // 后缀:234*+82/- : 10
    // 中后:8-(3+5-4/2)*2/3 : 83542/-+2*3/- : 4
    // 中后:2*(3+4)-8/2 : 234+*82/-
    

    运行截图:
    在这里插入图片描述

    展开全文
  • //用于指向字符串(中缀表达式)的指针 //声明两个栈,一个float型,一个char型 //表达式中操作数存在一个栈内,运算符存入一个栈内 //top1,top2用于指向两个栈的栈顶 float s1[maxSize];int top1=-1; char ...
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<math.h>
    #define Min 1e-8
    #define maxSize 10 
    int priority(char p){
    	 if(p=='+'||p=='-'){
    		return 0;
    	}else{
    		return 1;
    	}
    } 
    //子表达的计算 
    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){// 浮点数没有准确的表达,只能用绝对值来表示差不多的范围 
    			return 0;
    		}
    		else{
    			result =opand1/opand2;
    		}
    	} 
    	return 1;
    }
    int calStackTopTwo(float s1[],int &top1,char s2[],int &top2){
    	float a=s1[top1--];//弹出栈顶元素后指针下移 
    	float b=s1[top1--];
    	float result; 
    	char op=s2[top2--];
    	int flag=calSub(b,op,a,result);//进行子表达式的计算 
    	if(flag==0){
    		printf("被除数为零"); 
    		return 0;
    	}
    	s1[++top1]=result;//计算结果存入栈顶 
    	return 1;
    	
    } 
    //计算表达式的函数 
    float getResult(char exp[]){
    	int i=0;//用于指向字符串(中缀表达式)的指针 
    	//声明两个栈,一个float型,一个char型 
    	//表达式中操作数存在一个栈内,运算符存入一个栈内
    	//top1,top2用于指向两个栈的栈顶 
    	float s1[maxSize];int top1=-1; 
    	char s2[maxSize];int top2=-1;
    	
    	while(exp[i]!='\0'){//字符串结尾以'\0' 
    		if(exp[i]>='0'&&exp[i]<='9'){//判断是否是数字,但此处只能判断0-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(s2[top2]=='('||top2==-1||priority(exp[i])>priority(s2[top2])){
    				 		s2[++top2]=exp[i];
    				 		i++;
    					 }else{
    					 	int flag=calStackTopTwo(s1,top1,s2,top2);//当前运算符小于栈顶元素优先级则弹出数据栈的两个 
    						if(flag==0){
    							return 0;
    						}
    					 }                                  //操作数,进行运算后存入栈顶,完毕后i的值不发生 
    				 }                                      //变化 
    		 else if(exp[i]==')'){//如果碰到右括号,则弹出栈内直至左括号的所有运算符 
    		 	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];
    }
    //后缀表达式计算 
    float calPostFix(char exp[]){
    	float s1[maxSize];
    	int top=-1;
    	int i=0;
    	while(exp[i]!='\0'){
    		if(exp[i]>='0'&&exp[i]<='9'){
    			s1[++top]=exp[i]-'0';
    		}else{
    			float a,b,result;
    			a=s1[top--];
    			b=s1[top--];//出栈顶的两个元素 
    			int flag=calSub(a,exp[i],b,result);//子表达式计算结果存入result 
    			if(flag==0){
    				printf("Error");
    				return 0;
    			}
    			s1[++top]=result;//将结果存入栈顶 
    		}
    		i++;
    		 
    	}
    	return s1[top];
    	
    }
    float calPreFix(char exp[],int length){
    	float s1[maxSize];
    	int top=-1;
    	for(int i=length-1;i>=0;--i){
    		if(exp[i] >= '0' && exp[i]<='9'){
    			//printf("%c",exp[i]);
    			s1[++top]=exp[i]-'0';
    		}else
    		{   
    			float a,b,result;
    			a=s1[top--];
    			b=s1[top--];//出栈顶的两个元素 
    		//	printf("%f %f",s1[0],s1[1]);
    			int flag=calSub(a,exp[i],b,result);//子表达式计算结果存入result 
    			if(flag==0){
    				printf("Error");
    				return 0;
    			}
    			s1[++top]=result;//将结果存入栈顶 
    		} 
    	}
    	return s1[top];	
    }
    //中缀式转后缀式 
    //参数top传引用型是为了能够查看栈的最大用量 
    //参数s2[]数组是存储结果表达式 
    void infixtoPostFix(char infix[],char s2[],int &top2){
    	char s1[maxSize];//辅助栈 
    	int i=0,top1=-1; 
    	while(infix[i]!='\0'){
    		
    		if(infix[i]<='9'&&infix[i]>='0'){
    			s2[++top2]=infix[i];
    			i++;
    		}else if(infix[i]=='('){
    			s1[++top1]=infix[i];
    		
    			i++;
    		}else if(infix[i]=='*'||infix[i]=='+'||infix[i]=='-'||infix[i]=='/'){
    			if(top1==-1||s1[top1]=='('||priority(infix[i])>priority(s1[top1])){
    				//中缀转后缀,当前运算符优先级小于等于栈顶运算符优先级则出栈 
    				s1[++top1]=infix[i];
    				i++;
    			}else{
    				s2[++top2]=s1[top1--];
    			}
    		}else if(infix[i]==')'){
    			while(s1[top1]!='('){
    				s2[++top2]=s1[top1--];
    				
    			}
    			--top1;//
    			i++;
    		}
    	} 
    	while(top1!=-1){
    		s2[++top2]=s1[top1--];
    		
    	}
    }
    //中缀式转前缀式
    void infixtoPreFix(char infix[],int length,char s3[],int &top2){
    	char s1[maxSize];//辅助栈 
    	char s2[maxSize];// 
    	int i=length-1,top1=-1; 
    	while(i>=0){
    		if(infix[i]<='9'&&infix[i]>='0'){
    			s2[++top2]=infix[i];
    			i--;
    		}else if(infix[i]==')'){
    			s1[++top1]=infix[i];
    			i--;
    		}else if(infix[i]=='*'||infix[i]=='+'||infix[i]=='-'||infix[i]=='/'){
    			//中缀转前缀,当前运算符优先级小于栈顶运算符优先级则出栈 
    			if(top1==-1||s1[top1]==')'||priority(infix[i]) >= priority(s1[top1])){
    				s1[++top1]=infix[i];
    				i--;
    			}else{
    				s2[++top2]=s1[top1--];
    			}
    		}else if(infix[i]=='('){
    			while(s1[top1]!=')'){
    				s2[++top2]=s1[top1--];		
    			}
    			--top1;
    			i--;
    		}
    	} 
    	while(top1!= -1){
    		s2[++top2]=s1[top1--];	
    	}
    	int v=0;
    	for(int i=top2;i>=0;i--){
    		
    		s3[v++]=s2[i];
    	}
    
    }
    int getlength(char s[]){
    	int length=0;
    	for(int i=0;i<maxSize;i++){
    	   if((s[i]<'9'&&s[i]>'0')||s[i]=='+'||s[i]=='*'||
    	        s[i]=='/'||s[i]=='-'||s[i]=='('||s[i]==')'){
    	   	length++;
    	   }	
    	}
    	return length;
    }
    int main(){
    	char s[maxSize];
    	printf("请输入中缀表达式:\n");
    	scanf("%s",s);//录入字符串 
    	printf("%s=%f\n",s,getResult(s));
    	
    	char result[maxSize];//存放转换后结果 
    	int top1=-1;
    	infixtoPostFix(s,result,top1); 
    	printf("中缀转后缀为:%s\n",result);
    	printf("后缀的结果表达式为:%f\n",calPostFix(result));
    	int top2=-1;
    	char result1[maxSize];//存放转换后结果 
    	
    	infixtoPreFix(s,getlength(s),result1,top2); 
    	printf("中缀转前缀为:%s\n",result1);
    	printf("前缀的结果表达式为:%f\n",calPreFix(result1,getlength(s)));
    	
    }

    代码运行截图:

    其中在转化时需要注意:

    展开全文
  • 首先要知道什么是前缀表达式,什么是中缀表达式,什么是后缀表达式 所谓的中缀表达式就是类似于这种的运算1+((2+3)×4)-5 所谓的前缀表达式就是符号在两个操作数的前面- + 1 × + 2 3 4 5 所谓的后缀表达式就是两...

    首先要知道什么是前缀表达式,什么是中缀表达式,什么是后缀表达式

    所谓的中缀表达式就是类似于这种的运算 1+((2+3)×4)-5

    所谓的前缀表达式就是符号在两个操作数的前面 - + 1 × + 2 3 4 5

    所谓的后缀表达式就是两个数在运算符的右边 3 4 + 5 × 6 -

    这样我们就知道了前中后缀表达式所代表的含义是什么,在我们人的脑子看来,这个是一个很简单的运算操作,但是你要把他放在电脑上面,中缀表达式我感觉是比较难的,因为你要考虑运算符的优先级,括号的情况等等,我们可以将其转换成为前缀表达式或者后缀表达式来进行操作,其实原理都是一样的。

    我们这里用前缀表达式做例子:

    我们使用一个栈来运算,我们的优先顺序是从右往左遍历

    1. 当遇到数字的时候,压栈
    2. 当遇到运算符的时候,栈顶的两个元素出栈,计算之后再入栈

    就像我们的

    -×+3456
    1. 遇到6,压栈
    2. 遇到5,压栈
    3. 遇到4,压栈
    4. 遇到3,压栈
    5. 遇到+,取出栈顶的3和4,计算之后,压栈
    6. 遇到*,取出栈顶的7和5,计算之后,压栈
    7. 遇到-,取出栈顶的35和6,计算之后,压栈
    8. 最后存在栈里面的就是最终的结果
    package com.zhongruan.testDemo;
    
    import java.util.*;
    
    /**
     * @author weirdo
     * @date 2020-10-30 11:24
     * @email 1435380700@qq.com
     */
    public class Main {
    
        public static void main(String[] args) {
    
            Main m = new Main();
            String str = "-×+3456";
            System.out.println(m.preCalculate(str));
    
        }
    
        /**
         * 通过前缀表达式求值
         * 从右到左扫描,扫到数字进栈,扫到操作运算符就取出两个,进行计算然后压栈
         * @param str
         * @return
         */
        public int preCalculate(String str){
            //bianli
            Stack<Integer> number = new Stack<>();
            for(int i=str.length()-1;i>=0;i--){
                if(str.charAt(i)>='0' && str.charAt(i)<='9'){
                    number.push(str.charAt(i)-'0');
                }else{
                    switch (str.charAt(i)){
                        case '+':{
                            int num1 = number.pop();
                            int num2 = number.pop();
                            number.push(num1+num2);
                            break;
                        }
                        case '-':{
                            int num1 = number.pop();
                            int num2 = number.pop();
                            number.push(num1-num2);
                            break;
                        }
                        case '×':{
                            int num1 = number.pop();
                            int num2 = number.pop();
                            number.push(num1*num2);
                            break;
                        }
                        case '/':{
                            int num1 = number.pop();
                            int num2 = number.pop();
                            number.push(num1/num2);
                            break;
                        }
                        default:
                            break;
                    }
                }
            }
            //最后应该只剩下一个数字
            return number.pop();
        }
    
        
    
    }
    

    那么我们的中缀表达式这么变成前缀表达式/后缀表达式呢?其实都是一样的,一个正序,一个倒序。。

    我们使用两个栈,stack1 和 stack2 来存储

    1. 将前缀表达式从后往前遍历,如果当前的是数字的话,压入stack1
    2. 如果是操作运算符的话,且stack2为空的话,直接压栈
    3. 否则则要比较运算符的优先级(第一优先级()、第二优先级* /、第三优先级 + -)
    4. 如果当前的优先级比栈顶的运算符优先级高的话,则栈顶的运算符出栈stack1.push(stack2.pop());
    5. 最后将stack2种的数字压入stack1,得到的就是后缀表达式,反转一下就是前缀表达式

     

    package com.zhongruan.testDemo;
    
    import java.util.*;
    
    /**
     * @author weirdo
     * @date 2020-10-30 11:24
     * @email 1435380700@qq.com
     */
    public class Main {
    
        public static void main(String[] args) {
    
            Main m = new Main();
    //        String str = "-×+3456";
    //        System.out.println(m.preCalculate(str));
            System.out.println(m.toPreExpression("1+((2+3)*4)-5"));
            System.out.println("- + 1 × + 2 3 4 5");
    
        }
    
        /**
         * 通过前缀表达式求值
         * 从右到左扫描,扫到数字进栈,扫到操作运算符就取出两个,进行计算然后压栈
         * @param str
         * @return
         */
        public int preCalculate(String str){
            //bianli
            Stack<Integer> number = new Stack<>();
            for(int i=str.length()-1;i>=0;i--){
                if(str.charAt(i)>='0' && str.charAt(i)<='9'){
                    number.push(str.charAt(i)-'0');
                }else{
                    switch (str.charAt(i)){
                        case '+':{
                            int num1 = number.pop();
                            int num2 = number.pop();
                            number.push(num1+num2);
                            break;
                        }
                        case '-':{
                            int num1 = number.pop();
                            int num2 = number.pop();
                            number.push(num1-num2);
                            break;
                        }
                        case '×':{
                            int num1 = number.pop();
                            int num2 = number.pop();
                            number.push(num1*num2);
                            break;
                        }
                        case '/':{
                            int num1 = number.pop();
                            int num2 = number.pop();
                            number.push(num1/num2);
                            break;
                        }
                        default:
                            break;
                    }
                }
            }
            //最后应该只剩下一个数字
            return number.pop();
        }
    
        /**
         * 中缀表达式转化成为前缀表达式
         * @return
         */
        public String toPreExpression(String str){
    
            Map<Character,Integer> map = new HashMap<>();
            map.put('+',0);
            map.put('-',0);
            map.put('*',1);
            map.put('/',1);
            map.put(')',2);
            Stack<Character> stack1 = new Stack<>();
            Stack<Character> stack2 = new Stack<>();
            for(int i=str.length()-1;i>=0;i--){
                char c = str.charAt(i);
                if(c >='0' && c <='9'){
                    //如果是数字
                    stack1.push(c);
                }else{
                    if(stack2.isEmpty()){
                        stack2.push(c);
                    }else{
                        if(c==')'){
                            stack2.push(c);
                        }else if(c=='('){
                            while (stack2.peek()!=')' && !stack2.isEmpty()){
                                stack1.push(stack2.pop());
                            }
                            stack2.pop();
                        }else{
                            //比较运算符优先级
                            while (!stack2.isEmpty() && map.get(stack2.peek())<map.get(c)){
                                stack1.push(stack2.pop());
                            }
                            stack2.push(c);
                        }
    
    
                    }
                }
            }
            while (!stack2.isEmpty()){
                stack1.push(stack2.pop());
            }
            return stack1.toString();
        }
    
    }
    
    

     

    展开全文
  • 中缀表达式计算C++实现
  • 中缀表达式计算程序,手动实现运算数栈和运算符栈。
  • 主要问题:两位数或者多位数怎么办? 答案:找到一个数字时,继续向...中缀转化为后缀: package text_6; public class Queue { private Object[] original; private int startLength=20; private int f...

    主要问题:两位数或者多位数怎么办?

    答案:找到一个数字时,继续向后扫描,直到不是数字;将扫描到的拼成一个数字,在后缀字符串post中以#号分割

    中缀转化为后缀:

     

     

    package text_6;
    
    public class Queue {
    	private Object[] original;
    	private int startLength=20;
    	private int front;
    	private int rear;
    	
    	public Queue() {
    		original=new Object[startLength];
    		this.front = 0;
    		this.rear = 0;
    	}
    	public Object[] getOriginal() {
    		return original;
    	}
    	public void setOriginal(Object[] original) {
    		this.original = original;
    	}
    	public int getFront() {
    		return front;
    	}
    	public void setFront(int front) {
    		this.front = front;
    	}
    	public int getRear() {
    		return rear;
    	}
    	public void setRear(int rear) {
    		this.rear = rear;
    	}
    	
    }
    

     

    package text_6;
    
    import java.io.IOException;
    
    //import javax.print.attribute.standard.OrientationRequested;
    
    public class Operation {
    	private Queue queue;
    	private Object[] Original;
    	private int startLength=20;
    	private int top;
    	private int[] Nunber;
    	private char[] Char;
    	static int flag=0;
    	public int Gettop(){
    		return top;
    	}
    	/*
    	 * 初始化所建立的对象的数组长度和top
    	 */
    	public Operation(){
    		Original=new Object[startLength];
    		this.top=0;
    		this.queue=new Queue();
    	}
    	/*
    	 * 入队
    	 */
    	public void EnQueue(Object object){
    		Object[] original=queue.getOriginal();
    		if(queue.getFront()==queue.getRear()){
    			original[0]=object;
    			queue.setRear(queue.getRear()+1);
    		}else{
    			original[queue.getRear()]=object;
    			queue.setRear(queue.getRear()+1);		
    		}
    		
    	}
    	/*
    	 * 出队
    	 */
    	public Object DeQueue(){
    		Object[] original=queue.getOriginal();
    		int front=queue.getFront();
    		if(queue.getRear()==0){
    			System.out.println("空队");
    			return null;
    		}else{
    			
    			queue.setFront(queue.getFront()+1);
    			return original[front];
    //			return object;
    		}
    	}
    	public Object GetRear(){
    		Object[] original=queue.getOriginal();
    		if(queue.getRear()==0){
    			System.out.println("空队");
    			return null;
    		}else{
    			return original[queue.getRear()-1];
    		}
    	}
    	/*
    	 * 进栈,top上移
    	 */
    	public void Push(Object object){
    		if(this.top==0){
    			this.Original[0]=object;
    			this.top++;
    		}else{
    			Original[this.top]=object;
    			this.top++;
    		}
    	}
    	/*
    	 * 出栈,并且top的值下移
    	 */
    	public Object Pop(){
    		if(this.top==0){
    			System.out.println("次栈是空栈");
    			return null;
    		}else{
    			Object object=Original[this.top-1];
    			this.top--;
    			return object;
    		}
    	}
    	public Object getTop(){
    		if(this.Gettop()==0){
    			System.out.println("空栈");
    			return null;
    		}else{
    			Object object=this.Original[this.top-1];
    			return object;
    		}
    		
    	}
    	
    	
    	/*
    	 * 判断并返回两个运算符之间的优先级
    	 */
    	public int  priority(char n,char m){
    		int flag=1;
    		char [][] compare=new char[7][7];
    		
    		return flag;
    	}
    	static public int Operator(int m,int n,char Char){
    		if(Char=='+'||Char=='-'||Char=='*'||Char=='/'){
    			switch(Char){
    				case '*':
    					return m*n;
    				case '/':
    					if(n==0){
    						flag=1;
    						System.out.println("除0错误操作");
    						return 000;
    					}
    					return m/n;
    				case '+':
    					return m+n;
    				case '-':
    					return m-n;
    				default:
    					return 0;
    			}
    		}
    		else{
    			System.out.println("非法标志符");
    			return 000;
    		}
    //		return Char;
    	}
    	/*
    	 * 若s1优先则返回>,若s2优先则返回<,若s1,s2相同则返回=
    	 */
    	static public char Precede(char s1,char s2)
    	{
    		char f = 0;
    		switch(s2)
    		{
    			case '+':
    			case '-': 
    				if(s1=='('|| s1=='#')
    					f='<';
    				else
    					f='>';
    				break;
    			case '*':
    			case '/': 
    				if(s1=='*'||s1=='/'||s1==')')
    					f='>';
    				else
    					f='<';
    				break;
    			case '(':
    					f='<';
    				break;
    			case ')': 
    					f='>';
    				break;
    			case '#':
    				if(s1=='#')
    					f='=';
    				else
    					f='>';
    				break;
    			default :
    				break;
    		}
    		return f;
    	} 
    	public char[] InputChar() throws IOException{
    		char[] in = new char [20];
    		int i=0;//输入的字符数组的长度。
    		System.out.println("请输入字符:");
    		char ch=(char)System.in.read();
    		while(ch!='#'){
    			in[i]=ch;
    			i++;  
    			ch=(char)System.in.read();
    		}
    		return in;
    	}
    	/*
    	 *中缀计算 
    	 */
    	public int during(char[] in){
    		Operation operation=new Operation();
    		Operation number=new Operation();
    		operation.Push('#');
    		number.Push('#');
    		int x=0,y=0;
    		for(int j=0;j<in.length;j++){
    			char c=in[j];
    			if(c>='0' && c<='9'){
    				number.Push((int)c-48);System.out.println("           "+number.getTop());
    			}else{
    					char s1=(char)operation.getTop();
    					switch(Precede(s1,c)){
    					case '>':
    						if(c==')'){
    							for(int i=operation.Gettop()-1;i>=0;i--){
    								char c1=(char)operation.getTop();
    								if(c1=='('){
    									operation.Pop();
    									break;
    								}
    								operation.Pop();
    								x=(int)(number.Pop());
    								y=(int)(number.Pop());
    								number.Push(Operator(y,x,c1));System.out.println("             "+number.getTop());
    							}
    							
    						}else{
    							x=(int)(number.Pop());
    							y=(int)(number.Pop());
    							number.Push(Operator(y, x, s1));System.out.println("             "+number.getTop());
    							operation.Pop();
    							operation.Push(c);
    							
    						}
    						break;
    					case '<':
    						operation.Push(c);
    						break;
    					case '=':
    						//operation.Pop();
    						break;
    					default:
    						break;
    				}	
    			}
    		}
    		for(int i=operation.Gettop();i>=0;i--){
    			char c1=(char)operation.getTop();
    			if(c1=='#'){
    				break;
    			}
    			x=(int)(number.Pop());
    			y=(int)(number.Pop());
    			number.Push(Operator(y,x,c1));System.out.println("             "+number.getTop());
    			operation.Pop();
    		}
    		return (int)number.Pop();
    	}
    
    
    	/*
    	 * 中缀表达式转化成后缀表达式
    	 */
    	 public Operation Input(char[] in) throws IOException{
    		Operation operation=new Operation();
    		Operation number=new Operation();
    		Operation End=new Operation();
    		operation.Push('#');
    		number.Push('#');
    		for(int j=0;j<in.length;j++){
    			char c=in[j];
    			if(c>=48 && c<=57){
    				System.out.println(c);
    				End.EnQueue(c);
    //				End.Push(c);System.out.print("End  "+End.getTop());
    			}else{
    				if(operation.Gettop()==0){
    					operation.Push(c);
    				}else{
    					char s1=(char)operation.getTop();
    					switch(Precede(s1,c)){
    					case '>':
    						if(c==')'){
    							for(int k=operation.top-1;k>=0;k--){
    								char c1=(char)operation.getTop();
    								if(c1=='('){
    									operation.Pop();
    									break;
    								}
    								End.EnQueue(operation.getTop());
    //								End.Push(operation.getTop());System.out.print("End  "+End.getTop());
    								System.out.println(operation.Pop());
    							}
    						}else{
    //								End.Push(operation.getTop());System.out.print("End  "+End.getTop());
    								End.EnQueue(operation.getTop());
    								System.out.println(operation.Pop());
    								char c2=(char)operation.getTop();
    								if(Precede(c2, c)=='>'){
    //									End.Push(operation.getTop());System.out.print("End  "+End.getTop());
    									End.EnQueue(operation.getTop());
    									System.out.println(operation.Pop());
    								}	
    								operation.Push(c);							
    						}
    						break;
    					case '<':
    						operation.Push(c);
    						break;
    					}
    				}	
    			}
    //			System.out.println("   "+j);
    		}
    		System.out.println("栈顶"+operation.Gettop());
    		for(int j=operation.top-1;j>0;j--){
    			System.out.println(operation.Original[j]);
    			End.EnQueue(operation.Original[j]);
    		}
    		return End;
    	}
    	 /*
    	  * 
    	  */
    	 public void front_count(){
    		 
    	 }
    	 /*
    	  * 后缀表达式计算;
    	  */
    	 public void back_count(){
    			Operation back_CPush=new Operation();
    			Object object=null;int x=0,y=0;
    			for(int i=0;i<this.queue.getRear();i++){
    				object=this.DeQueue();
    				if(object instanceof Character){//如果obj是字符类型
    					char c = (char)object;//进行强制类型转换
    					if(c>='0' && c<='9'){
    						back_CPush.Push((int)c-48);
    					}else{
    //						System.out.println("shazi"+y+c+x);
    						x=(int)back_CPush.Pop();
    						y=(int)back_CPush.Pop();
    						back_CPush.Push(Operator(y, x, c));
    					}
    				}
    			}
    			System.out.println("     "+back_CPush.Pop());	
    		}
    	 
    	 public void system_Queue(){
    		 System.out.println("输出队中的元素");
    		 for(int i=0;i<queue.getRear();i++){
    			 System.out.println(this.DeQueue());
    		 }
    		 
    	 }
    	 
    	 public void system_Push(Operation back_conut){
    		 int i;
    		 System.out.println("多少呀"+back_conut.Gettop());
    		 for(i=0;i<back_conut.Gettop();i++){
    			 System.out	.println(back_conut.getTop()+"  "+i);
    			 back_conut.Pop();
    		 }
    		 System.out.println("   ghl"+i);
    	 }
    	 
    	public static void main(String[] args) throws IOException {
    //        BigDecimal b = new BigDecimal("20").divide(new BigDecimal("3"), 3, BigDecimal.ROUND_UP);
    //        System.out.println( b );
    		Operation link=new Operation();
    		Operation back_opereator=new Operation();
    		char[] in=link.InputChar();
    //		back_opereator=link.Input(in);//中缀到后缀
    //		back_opereato   r.system_Queue();//输出后缀队列
    //		back_opereator.back_count();//后缀计算
    		
    		System.out.println(link.during(in));
        }
    //(3-1+2)*2+1-3#
    }
    

     

    展开全文
  • 邓俊辉数据结构 栈应用之 中缀表达式计算 学堂在线教学视频 堆栈应用之一,在线性扫描类算法中当读到足够长之后,方可处理前缀。应用在计算器中。 #include <iostream> #include "Stack.hpp" #include <...
  • 中缀表达式计算组件,支持运算符:+ - * / ^,同时支持括号运算,及中缀表达式合法性的检查并定位错误.这里提供组件源码及用这个组件开发的计算器(VC++6.0开发) 附: 这个组件为测试版本,在应用于MFC项目时候,可能会出现...
  • c语言中缀表达式计算

    2015-01-03 18:15:23
    利用c语言写的中缀表达式,主要数据结构是栈。
  • 有关中缀表达式计算是数据结构中非常经典的题目,以至于很多文章或课本喜欢直接给出计算方法一步到位,但关于其中的原理却并未深究,本文试图通过分析运算符的栈内优先级,栈外优先级的排序方法探求中缀表达式计算...
  • 本文主要介绍中缀表达式计算机求值算法和代码实现
  • 中缀表达式概念: 中缀表达式是一个通用的算术或逻辑公式表示方法, 操作符是以中缀形式处于操作数的中间(例:3 + 4),中缀表达式是人们常用的算术表示方法。例如:1+2*18-3的形式 代码实现: 1)创建工具类,...
  • Java中缀表达式计算

    2020-01-28 17:40:29
    表达式计算(中缀表达式) 1. 分析 通过index索引遍历表达式 如果发现为数字则入数字栈 如果扫描到为符号则: 如果符号栈为空则直接入栈 如果符号栈不为空,则进行比较:如果当前符号优先级小于或...
  • 数据结构与算法实验4(栈应用)中缀表达式计算 栈ADT应用:中缀表达式求值 表达式求值是进行数据处理的最基本操作。请编写程序完成一个简单算术表达式的求值。要求如下: (1)运算符包括:+、-、*、-、^...
  • 这是用c#写的一个计算器,实现了中缀表达式计算
  • 中缀表达式:操作符在操作数中间;例如:1+2*3-4/5 后缀表达式:操作符在操作数后面;例如:1 2 3 * 4 5 / - + 后缀表达式的优点:按顺序读取,碰到操作数进栈;碰到操作符就把前面两个操作数弹出来计算计算结果...
  • Java实现中最表达式计算 支持整数,负数,需要正确输入。 import java.util.Scanner; import java.util.Stack; public class Main { public static void main(String[] args) { Scanner input = new Scanner(System...
  • 中缀表达式计算(可以处理括号),实现简单的计算功能,让你在简单的问题中学会栈的复杂知识
  • 输入常规表达式后,自动转换成中缀表达式,并计算结果。C语言实现,原创代码,欢迎下载。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,525
精华内容 1,410
关键字:

中缀表达式计算