精华内容
下载资源
问答
  • 中缀转后缀

    2016-05-04 11:41:31
    中缀转后缀
    #include<iostream>
    #include<stdio.h>
    #include<cstring>
    #include<stack>
    using namespace std;
    int first(char b)
    {
        if(b=='(') return 0;
        else if(b=='+'||b=='-') return 1;
        else if(b=='*'||b=='/') return 2;
    }
    int main()
    {
        int k;
        char a[200];
        scanf("%d",&k);
        getchar();
        while(k--)
        {
            gets(a);
            stack<char>s;
            for(int i=0; i<strlen(a); i++)
            {
                if(a[i]>='0'&&a[i]<='9') printf("%c ",a[i]);
                else if(a[i]=='(') s.push(a[i]);
                else if(a[i]==')')
                {
                    while(s.top()!='(')
                    {
                        printf("%c ",s.top());
                        s.pop();
                    }
                    s.pop();
                }
                else if(a[i]=='+'||a[i]=='-'||a[i]=='*'||a[i]=='/')
                {
                    if(!s.empty())
                    {
                        while(!s.empty()&&first(a[i])<=first(s.top()))
                        {
                            printf("%c ",a[i]);
                            s.pop();
                        }
                    }
                    s.push(a[i]);
                }
            }
            while(!s.empty())
            {
                printf("%c ",s.top());
                s.pop();
            }
            printf("\n");
        }
        return 0;
    }
    
    

    引用文章地址:

    http://cc.siso.edu.cn/ds/16.html

    • -


    展开全文
  • public class Test {/*** 一:非运算符直接输出* 二:遇到左括号直接入栈* 三:栈顶...左括号出栈抛弃* :乘除优先级相等》 加减优先级相等** 中缀转后缀实例,支持10以内加减法** */public static void main(Strin...

    public class Test {

    /**

    * 一:非运算符直接输出

    * 二:遇到左括号直接入栈

    * 三:栈顶符号优先级高于或等于即将入栈的操作符,则将高于和等于的操作符出栈,然后再入栈

    * 四:遇右括号,输出栈中的运算符,直到遇到第一个左括号,左括号出栈抛弃

    * :乘除优先级相等》 加减优先级相等

    *

    * 中缀转后缀实例,支持10以内加减法

    *

    * */

    public static void main(String[] args) {

    String s="2+2*3/((2*(1+2)-4)*5)";

    char[]chars=s.toCharArray();

    Stack stack=new Stack<>();

    ArrayList list=new ArrayList<>();

    for(int i=0;i

    char m=chars[i];

    //System.out.println(m);

    if(m!='+'&&m!='-'&&m!='*'&&m!='/'&&m!='('&&m!=')'){

    list.add(m);

    }else{

    if(stack.isEmpty()&&m!=')'){

    stack.push(m);

    }else{

    if(m==')'){

    /**

    * 清除一对括号

    * */

    while((char)stack.peek()!='('){

    list.add(stack.pop());

    }

    stack.pop();

    }else if(m=='('){

    stack.push(m);

    }else{

    popContinue(m, stack, list);//最多执行两次,除了(左括号外,栈内不会有两个连续权限相等的符号

    }

    }

    }

    }

    while(!stack.isEmpty()){

    list.add(stack.pop());

    }

    System.out.println(list.toString());

    Stack res=new Stack();

    for(int i=0;i

    char m=(char)list.get(i);

    if(m!='+'&&m!='*'&&m!='-'&&m!='/'){

    res.push(Double.parseDouble(m+""));

    }else{

    double d1=0,d2=0;

    if(!res.isEmpty()){

    d1=(double) res.pop();

    }

    if(!res.isEmpty()){

    d2= (double) res.pop();

    }

    double d3 = 0;

    if(m=='*'){

    d3=d2*d1;

    }

    if(m=='+'){

    d3=d2+d1;

    }

    if(m=='-'){

    d3=d2-d1;

    }

    if(m=='/'){

    d3=d2/d1;

    }

    res.push(d3);

    }

    }

    System.out.println(res.pop());

    }

    public static void popContinue(char m,Stack stack,ArrayList list){

    int v1=getValues(m);

    int v2=getValues((char)stack.peek());

    if(v1>v2){

    stack.push(m);

    return ;

    }else{

    list.add(stack.pop());

    if(!stack.isEmpty()){

    popContinue(m, stack, list);

    }else{

    stack.push(m);

    }

    }

    }

    public static int getValues(char m){

    int i=0;

    if(m=='*'||m=='/'){

    i=2;

    }else if(m=='('){

    i=0;

    }else{

    i=1;

    }

    return i;

    }

    }

    展开全文
  • 本文主要向大家介绍了JAVA语言中缀转后缀表达式代码,通过具体的内容向大家展示,希望对大家学习JAVA语言有所帮助。看了网上其他人写的感觉好复杂,难以理解,我感觉我的实现很简单,容易明白,可以借鉴!哈哈注释很...

    本文主要向大家介绍了JAVA语言中缀转后缀表达式代码,通过具体的内容向大家展示,希望对大家学习JAVA语言有所帮助。

    看了网上其他人写的感觉好复杂,难以理解,我感觉我的实现很简单,容易明白,可以借鉴!哈哈

    注释很全,不解释了public class Demo {

    @Test

    public void main(){

    String hou = zhongTransHou("2+((1-3)*4)-2");

    System.out.println(hou);

    }

    public String zhongTransHou(String zhong){

    //创建一个栈存放运算符使用

    Stack ysfz = new Stack();

    StringBuilder hz = new StringBuilder();

    //扫描整个运算表达式

    char[] chars = zhong.toCharArray();

    for (char c : chars) {

    //当前扫描的是运算符

    if(c == '+' || c== '-' || c== '*' || c=='/'||c==')'||c=='('){

    //进行优先级和右括号的判断

    //如果当前元素是右括号的话

    if(c == ')'){

    while(ysfz.peek()!='('){//遍历部分栈,只要栈顶不是"("都要出战,并且匹配到"("本身也要出栈

    char top = ysfz.pop();//移除栈顶元素并返回移除的值

    hz.append(top);

    }

    //执行到这里说明已经清空了所有的在"("上面的运算符,此后将本身也给清楚

    ysfz.pop();

    }else if(ysfz.isEmpty()){//当前栈是空的话

    ysfz.push(c);//直接入栈

    }else if(curYSFIsGao(c,ysfz)){//当前运算符比栈顶运算符高的话

    ysfz.add(c);

    }else if(!curYSFIsGao(c,ysfz)){//当前运算符比栈顶运算符低的话

    while(!ysfz.isEmpty()){//遍历整个栈

    char top = ysfz.pop();

    hz.append(top);

    }

    //执行到这里栈已经是空了,现在将当前元素入栈

    ysfz.push(c);

    }

    }else{//当前扫描的数字

    hz.append(c);

    }

    }

    //真个表达式扫描之后,出栈

    while(!ysfz.isEmpty()){

    char top = ysfz.pop();

    hz.append(top);

    }

    return hz.toString();

    }

    /**

    * 判断当前元素和栈顶元素的优先级,这里面间接的判断如果是“(”也是入栈(优先级高就入栈)

    * @param c

    * @param ysfz

    * @return

    */

    private boolean curYSFIsGao(char c,Stack ysfz) {

    boolean isGao = true;//默认是高

    //拿取栈顶元素,和当前传入元素做比较优先级

    char top = ysfz.peek();

    if(c == '+' || c == '-'){

    if(top == '*' || top == '/'){

    isGao = false;

    }

    //遇到加减或者"("默认高

    }

    //当前是乘除的话默认高,也就是都向栈里面添加

    return isGao;

    }

    }

    本文由职坐标整理并发布,希望对同学们有所帮助。了解更多详情请关注编程语言JAVA频道!

    展开全文
  • 表达式中缀转后缀C++代码表达式中缀转后缀C++代码表达式中缀转后缀C++代码表达式中缀转后缀C++代码表达式中缀转后缀C++代码表达式中缀转后缀C++代码表达式中缀转后缀C++代码表达式中缀转后缀C++代码表达式中缀转后缀...
  • 从书上看到的讲起最近(半年内 )在看《大话数据结构》,上个星期在栈这一节看到了后缀表达式用于...后缀表达式求值规则(《大话数据结构》)中缀转后缀规则(《大话数据结构》)当尝试了之后发现,上面的描述没有...

    从书上看到的讲起

    最近(半年内 )在看《大话数据结构》,上个星期在栈这一节看到了后缀表达式用于计算的神奇力量。于是用Python试着实现了一下(功底太差,导致花了很长时间)。后缀表达式求值很容易实现,基本就是进栈、出栈和求值,简单一个函数就搞定了。然而中缀转后缀表达式的规则,书上写的似乎有些疏漏。

    34ce9b71efb2ff055e2bb1af24e3ad57.png
    后缀表达式求值规则(《大话数据结构》)

    b31731b5f6ad9c6002f789914331584d.png
    中缀转后缀规则(《大话数据结构》)

    当尝试了之后发现,上面的描述没有给出若被遍历的符号与栈顶符号同优先级该如何处理。其次,似乎只有当欲右括号时,才应将栈中左括号之前的符号全部出栈。尝试在Bing搜了些资料,没有找到想要的东西,于是在B站找了找,发现两个视频:

    • 中缀转后缀表达式(逆波兰式) 转 前缀表达式(波兰式)8分钟速成手工算法 数据结构栈 https://www.bilibili.com/video/BV1aJ411i7G7
    • 中缀表达式转后缀表达式 | 栈 https://www.bilibili.com/video/BV15g4y187sz

    前一个视频可以加深对于后缀表达式的理解,后一个视频给出了具体的算法。

    068cf23b07a4bdcf10744584a029a688.png
    后缀表达式的算法

    而这个算法就和我尝试的结果比较吻合,遇优先级相同的时候,也应该输出栈内符号。

    然后说说我的理解

    通过这些资料和对实现的尝试,我也对后缀表达式的原理有了一点浅显的理解,遂记之以备忘。

    在中缀转后缀的算法中,我们会遇到三个元素:数字、运算符和括号,遍历过程中,遇到数字直接输出,而利用栈来比较的是运算符和括号,所以实际上我们是通过比较运算符和括号来确定最终的运算顺序。下面通过几个例子来说明。

    • 例 1

    中缀:a+b

    对于这个中缀表达式,下面给出每一步比较符号的过程。其中最左边为当前输出的表达式。用中括号[]表示栈,右边是栈顶,栈的右边是当前遍历到的符号。因为遇到数字直接输出,而一个数字后面一般跟一个符号,所以将两步遍历写在一起。

    在遍历中,首先遇到数字a,将其直接输出,此时栈为空,然后遍历到加号,当前的状态是
    a [] +
    ----- -----
    加号入栈,然后遍历到数字b,将其直接输出,当前的状态是
    ab [+]
    ----- -----
    没有其他的符号,将栈中符号输出,于是得到最终的表达式
    ab+ []

    其中a和b可以看作是其他表达式的运算结果,比如下例。

    • 例 2

    中缀:a+c*d

    运算过程是:

    直接输出a,栈为空,遍历到加号
    a [] +
    ----- -----
    加号入栈,直接输出c,遍历到乘号
    ac [+] *
    ----- -----
    乘号的优先级比栈顶符号高,所以乘号入栈,直接输出d
    acd [+*]
    ----- -----
    没有其他符号,栈内符号依次出栈,于是得到最终输出:acd*+

    对于中缀表达式来说,由于乘法的优先级更高,所以要先计算c*d。这里可以将 c*d看作一个整体,相当于上一例中的b,即a+b,其中 b=c*d。

    也就是说,我们可以这样看:

    中缀          后缀
    a + c * d     a c d * +
    |   |_b_|     | |_b_| |
    |__a+b__|     |__ab+__|
    
    • 例 3

    中缀:a+c+d

    这一例中,前后两个符号的优先级相同,所以应该从左到右顺序求值。因为没有什么特别之处,所以就不作过多说明,快速的给出过程:

    a [] +
    ----- -----
    ac [+] +
    ----- -----
    优先级相同,栈顶符号出栈,然后加号入栈
    acd+ [+]
    ----- -----
    acd++ []
    • 例 4

    中缀:a-c+d

    先给出过程:

    a [] -
    ----- -----
    ac [-] +
    ----- -----
    由于加号与栈顶符号优先级相同,所以栈顶符号出栈,然后加号入栈;接下来遍历遇到数字d,直接输出。
    ac-d [+]
    ----- -----
    没有其他符号,栈内符号依次出栈。
    ac-d+ []

    这一例就有点不同了,因为两个符号的优先级相同,运算顺序必须从左到右,即(a-c)+d,将a-c视为一个整体;而如果不小心变成a-(c+d),将c+d视为一个整体,就产生错误了。

    a - c + d     a c - d +
    |___|   |     |___|   |
    |_______|     |_______|
    
                  错误(愿你不会遇到):
                  a c d + -
                  | |___| |
                  |_______|

    通过上面4个例子可以看到,对于一个长的表达式 a+c*d 或 a + b + c 等,通过计算优先级高的部分,或从左往右计算,最终总是会变成类似于 a + b(或a-b,或乘,或除以)的形式。也就是说,表达式中,两个数字和他们的运算符可以看作是一个整体,即一个数字。理解了这一点,应该就容易理解后缀表达式为什么能用来代替中缀表达式求值了。实际上中缀表达式也是如此,每次计算两个数,然后逐渐化为a+b的形式,而中缀表达式不需要括号,求值要方便很多。

    吐槽:在知乎发的第一篇文章。写完发现自己的表达能力还很欠缺,而且好像忘了自己要讲什么。anyway,希望有人看到之后会受到启发吧(或者被我弄得更糊涂了)。

    p.s 上面提到的B站的两个视频其实很不错的。

    展开全文
  • 1.基于上一播博客https://blog.csdn.net/notears0828/article/details/890477782.应用栈,实现将中缀转换成后缀表达是public class MyExpressionUtil {/*** 判断是否是操作符*/public static boolean isOperator...
  • 中缀转后缀中缀转后缀口诀:1.遇到操作数,直接输出。2.当栈为空时,遇到操作符直接入栈。3.遇到左括号,将其入栈4.遇到右括号,执行出栈,输出出栈的元素,直到弹出左括号,(左右括号不输出)。5.遇到运算符时,依次...
  • } /** * 将中缀表达式转换为后缀表达式的处理方法 * @param input 中缀表达式 2+3 * @return 后缀表达式 23+ */ public ArrayList doTrans(String input)throws Exception{ if(!validate(input)) { throw new ...
  • 缺点:目前只实现10以内的四则运算学到的知识点:StringBuffer如果想char数组,首先String,然后装CharString tem1=st.toString();char tem[]=tem1.toCharArray();如何将字符数字Float要使用包装类型Float....

空空如也

空空如也

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

中缀转后缀