将中缀表达式转换成后缀表达式并求值(栈)

时间:2021-05-04作者:klpeng分类:IT综合浏览:526评论:0

 中缀表达式转换成后缀表达式,和通过后缀表达式求值需要用到的是数据结构中的一种——栈。如果还不清楚栈是什么的,可以点击了解 : 数据结构栈

目录

为何需要转换为后缀表达式

一、中缀表达式转换成后缀表达式

二、通过后缀表达式求值


为何需要转换为后缀表达式

中缀表达式 : 生活中进行正常加减乘除计算的表达式。如2+(3*4-6/2)。也就是算术表达式

后缀表达式 :也叫逆波兰表达式。只有运算符和数字没有括号,运算符的先后顺序存在优先级的关系。如: 234*62*2+ 。

(由于需要处理字符串的原因,目前只有个位数的算术运算)

给出的算术表达式通过代码实现很难计算出来,而转换成了后缀表达式的就很容易实现出来了。

当然,以下代码是很容易的出计算结果的。

public class Main {
	
	public static void main(String[]args) {
		
		int a =2+(3*4-6/2);
		System.out.println(a); 
		
	}
}

哈哈,简单的一个表达式的计算,编译器很容易就能得出a的答案。

将中缀表达式转换成后缀表达式并求值(栈)

那么假如给出的算术表达式不固定,而是认为通过字符串的输入,那计算机如何识别出来并且准确的计算出来呢。

 

import java.util.Scanner;
public class Main {
	
	public static void main(String[]args) {
		Scanner sc = new Scanner(System.in);
		String a = sc.nextLine();
		System.out.println(a);
		
	}
}

 

一、中缀表达式转换成后缀表达式

所求出来的后缀表达式,只有1.运算符和2.数字,跟算术表达式就是少了一个括号优先级和多了相对的运算符优先级。用一个运算符栈来存储运算符,加一个能够求出的后缀表达式数组。两个都是char[]型,用来存储多个字符。那么此处就有很大的局限性,字符只能存储一个数字0~9,这样的话就导致了只能进行0~9的算术运算。后续也将记录如何处理10位数的算术运算。

首先,声明一个运算符栈MyStack和一个后缀表达式字符数组postxp。(栈MyStack来存储临时的运算符)(字符数组里的字符串就是所要求的后缀表达式)

以下遇到的运算符只有+-*/()。

1.从左往右扫描表达式,每个数和运算符都被认为是一个字符。

 (1)假如扫描到的是数字,直接放到postxp中,在进行以一个字符的扫描。例如当扫描到了2,3,4,6,2是直接放到postxp数组中。

 (2)假如扫描到的是运算符+,-,*,/ 的话,假如运算符栈内没有一个运算符,就直接压入栈中。如果运算符栈中有运算符,扫描到的当前的运算符就要跟栈顶运算符做算术优先级比较,假如当前运算符的算术优先级比栈顶运算符的优先级大,那么就直接压入栈中(将当前运算符放入栈中),假如比栈顶运算符的优先级是一样的或者小,那么出栈栈顶运算符将该运算符放到postxp数组中,然后当前运算符继续比较新的栈顶运算符。以此反复,直到能够放进栈中。

   (3)扫描到了最后一个字符后,假如栈中还有运算符,那么就依次全部出栈并且放到posetep中

特殊情况:当扫描到了 ( )时,不会被放入到postxp数组中,如果有运算符导致(为栈顶,那么(不会被出栈,当前运算符直接压入栈中,如果扫描到了) 右括号那么栈内必定会有(括号,那么出栈栈顶并且将栈顶运算符放入到postep数组中,直到栈顶为(时,(出栈,继续接下来的操作。

产生特殊情况的原因是()括号在算术运算中优先级太高了,*/都比不过,postxp数组基本上运算符的排列顺序从左到右,越左边的运算符就越早进行运算,这也是为什么栈顶往往都要比栈内的元素优先级大,因为栈的特性就是后进先出。运算符出栈都是被压入在了后缀表达式postxp数组中(除了()左右括号外)。

最后求出的postxp字符数组就是所要求得的后缀表达式。

那么,现在手写将中缀表达式转换成后缀表达式就不难了。

例如(5+1*2)/(4*2-4)转换为后缀表达式为512*+42*4-/。

二、通过后缀表达式求值

给出算术表达式的最终目的就是要求出表达式的值,只是对于计算机来说,转换成后缀表达式更加好求一点。另外,通过后缀表达式求值也是需要栈的,是存储数值的栈,当把后缀表达式postxp数组从左到右扫描完后,数值栈里面的最后的值就是其表达式运算求出来的值。

定义一个数值栈dataxp,另外一个是上面所求出的postxp后缀表达式。postxp依次从左到右扫描。

1.当扫描到的字符是数字时,压入data栈中,直到遇到运算符。

2.当扫描到的字符是运算符时,将data栈出栈两个数,进行扫描到的运算符操作,然后计算之后的值在压入栈中,相当于就是对栈顶的两个元素进行运算符计算,栈的元素--,保存数值在栈顶。

因为后缀表达式没有括号来影响运算符的优先级,所以只有上述的两种情况,当扫描完之后,栈的栈顶就是最后所需要求得的值啦。但是,这样的处理的话,也会出现一些弊端,那么就是确保后缀表达式是正确的,这样才能保证最后所求得的值是正确的;

通过后缀表达式求值的代码实现:

#include<iostream>

#include<string.h>

using namespace std;

#define MaxSize 100

typedef struct DataStack{

int data[MaxSize];

 int top;

 }DataStack;

int main()

 {

    DataStack d ;
    d.top=-1;
    char postxp[100];

    cout<<"请输入后缀表达式:";
    cin>>postxp;
    //cout<<postxp<<endl;
    int len = strlen(postxp);
    
    for(int i=0;i<len;i++)
    {
        if(postxp[i]>='0'&&postxp[i]<='9')
        {
            d.data[++d.top];
        }
        else if(postxp[i]=='+')
        {
            d.data[d.top-1] = d.data[d.top] +d.data[d.top-1];
            d.top--;
        }
        else if(postxp[i]=='-')
        {
            d.data[d.top-1] = d.data[d.top] -d.data[d.top-1];
            d.top--;
        }
        else if(postxp[i]=='*')
        {
            d.data[d.top-1] = d.data[d.top] *d.data[d.top-1];
            d.top--;
        }
            else if(postxp[i]=='/')
        {
            d.data[d.top-1] = d.data[d.top] /d.data[d.top-1];
            d.top--;
        }
    }

    cout<<"所得的值为:";
    cout<<d.data[d.top]<<endl;
    return 0;
}

输出结果:

将中缀表达式转换成后缀表达式并求值(栈)

 

 

打赏
文章版权声明:除非注明,否则均为彭超的博客原创文章,转载或复制请以超链接形式并注明出处。
相关推荐

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

猜你喜欢