精华内容
下载资源
问答
  • 接上篇中缀计算器的实现,这篇实现后缀表达式(逆波兰表达式)实现计算器,以及中缀表达式转换为后缀表达式。 后缀表达式计算器的实现 后缀表达式:3 4 + 5 * 6 - 实现思路: 只需要一个栈用来存储数值,在遍历的...

    开心学算法的第6天
    中缀表达式实现简易计算器
    接上篇中缀计算器的实现,这篇实现后缀表达式(逆波兰表达式)实现计算器,以及中缀表达式转换为后缀表达式。

    后缀表达式计算器的实现

    后缀表达式:3 4 + 5 * 6 -
    实现思路:

    只需要一个栈用来存储数值,在遍历的过程中遇到字符时就需要将数栈出栈两个元素并调用上一篇所实现的compute计算函数计算的值并将结果入栈,在遍历完成之后将结果入栈依次类推,最后栈中只剩余一个元素并且打印结果。

    	//后缀
        //从左向右依次入栈只存在一个数栈,如果遇到运算符则直接出栈两个元素,最后将计算结果入栈
        public static void afterCalculator(stack<Integer> number,String expression){
            String[] split = expression.split(" ");
            //后缀表达还是只需要一个栈
            for (int i = 0; i < split.length; i++) {
                if (split[i].matches("\\d+")){
                    //匹配多位数
                    number.push(Integer.valueOf(split[i]));
                }else {
                    //运算符
                    Character character = Character.valueOf(split[i].charAt(0));
                    //出两个数栈
                    int num1 = Integer.valueOf(number.pop());
                    int num2 = Integer.valueOf(number.pop());
                    int res = compute(num1, num2, character);
                    //将计算结果入栈
                    number.push(res);
                }
            }
            System.out.println(number.pop());
        }
    

    中缀表达式转化为后缀表达式

    实列:1+((2+3)*4)-5 ------------> 123+4*+5-

    首先先将字符串转为字符型的集合

    	//将字符串转换为集合
        private static List<String> strTransferList(String expression) {
            //结果集
            List<String> res = new ArrayList<>();
            //用来处理多位数
            int j = 0;
            for (int i = 0; i < expression.length(); i++) {
                if (Character.isDigit(expression.charAt(i))){
                    //用来处理多位数的缓存字符串
                    String str = String.valueOf(expression.charAt(i));
                    //表示的是数字
                    j = i + 1;
                    while (j < expression.length()){
                        if (Character.isDigit(expression.charAt(j))){
                            //表示的下一位字符仍然是数字,当前是一个多位数
                            str+=expression.charAt(j);
                        }else{
                            break;
                        }
                        j++;
                    }
                    //跳到下一个未遍历的
                    i = j - 1;
                    res.add(str);
                }else {
                    //非数字
                    res.add(String.valueOf(expression.charAt(i)));
                }
            }
            return res;
        }
    

    转换的过程

    实现思路:

    存在两个栈一个栈为结果栈res、还有一个中间栈stack,遍历字符集合,当遇到数字时直接入栈到res中,如果遇到‘(’括号直接入栈stack,当遇到‘)’,循环遍历stack中元素出栈并入栈到res,直至遇到’(’,最后出栈stack因为’('括号就要弃掉,如果遍历完以后发现stack不为空就要将其中的所有元素出栈并且入栈到res中,最后返回res,这样就可以办到中缀转换为后缀表达式。

    //中缀表达式转换为后缀表达式   1+((2+3)*4)-5
        public static void transfer(String expression){
            List<String> list = strTransferList(expression);
            stack<String> stack = new stack<>(10);
            stack<String> res = new stack<>(10);
            Iterator<String> iterator = list.iterator();
            while (iterator.hasNext()){
                String next = iterator.next();
                //开始判断数还是运算符
                if (next.matches("\\d+")){
                    //表示的数
                    res.push(next);
                } else if (next.equals("(")){
                    //不是数字
                    stack.push(next);
                }else if (next.equals(")")){
                    //表示括号里面的东西全部入栈res
                    while (!stack.peek().equals("(")){
                        res.push(stack.pop());
                    }
                    //出栈(
                    stack.pop();
                }else {
                    //符号栈不为null判断栈顶元素与当前运算符的优先级
                    while(!stack.isEmpty() && priority(stack.peek().charAt(0)) >= priority(next.charAt(0))){
                        res.push(stack.pop());
                    }
                    //当前操作符入栈
                    stack.push(next);
                }
            }
            //将剩余的符号栈中的元素全部出栈并入栈到结果栈
            while (!stack.isEmpty()){
                res.push(stack.pop());
            }
        }
    

    在这里插入图片描述

    点个赞呗~~~

    展开全文
  • 以下示例演示如何使用堆栈的概念将中缀转换为后缀表达式。package com.yiibai; import java.io.IOException; public class Infix2Postfix { private Stack theStack; private String input; pri...

    在Java编程中,如何将中缀表达式转换为后缀表达式?

    以下示例演示如何使用堆栈的概念将中缀转换为后缀表达式。

    package com.yiibai; import java.io.IOException; public class Infix2Postfix { private Stack theStack; private String input; private String output = ""; public Infix2Postfix(String in) { input = in; int stackSize = input.length(); theStack = new Stack(stackSize); } public String doTrans() { for (int j = 0; j < input.length(); j++) { char ch = input.charAt(j); switch (ch) { case '+': case '-': gotOper(ch, 1); break; case '*': case '/': gotOper(ch, 2); break; case '(': theStack.push(ch); break; case ')': gotParen(ch); break; default: output = output + ch; break; } } while (!theStack.isEmpty()) { output = output + theStack.pop(); } System.out.println(output); return output; } public void gotOper(char opThis, int prec1) { while (!theStack.isEmpty()) { char opTop = theStack.pop(); if (opTop == '(') { theStack.push(opTop); break; } else { int prec2; if (opTop == '+' || opTop == '-') prec2 = 1; else prec2 = 2; if (prec2 < prec1) { theStack.push(opTop); break; } else output = output + opTop; } } theStack.push(opThis); } public void gotParen(char ch) { while (!theStack.isEmpty()) { char chx = theStack.pop(); if (chx == '(') break; else output = output + chx; } } public static void main(String[] args) throws IOException { String input = "1+2*4/5-7+3/6"; String output; Infix2Postfix theTrans = new Infix2Postfix(input); output = theTrans.doTrans(); System.out.println("Postfix is " + output + 'n'); } class Stack { private int maxSize; private char[] stackArray; private int top; public Stack(int max) { maxSize = max; stackArray = new char[maxSize]; top = -1; } public void push(char j) { stackArray[++top] = j; } public char pop() { return stackArray[top--]; } public char peek() { return stackArray[top]; } public boolean isEmpty() { return (top == -1); } } }

    上述代码示例将产生以下结果 –

    124*5/+7-36/+ Postfix is 124*5/+7-36/+

    示例-2

    以下是将中缀表达式转换为后缀表达式的另一个例子

    package com.yiibai; import java.io.BufferedReader; import java.io.InputStreamReader; class MyStack { char stack1[] = new char[20]; int t; void push(char ch) { t++; stack1[t] = ch; } char pop() { char ch; ch = stack1[t]; t--; return ch; } int pre(char ch) { switch (ch) { case '-': return 1; case '+': return 1; case '*': return 2; case '/': return 2; } return 0; } boolean operator(char ch) { if (ch == '/' || ch == '*' || ch == '+' || ch == '-') return true; else return false; } boolean isAlpha(char ch) { if (ch >= 'a' && ch <= 'z' || ch >= '0' && ch == '9') return true; else return false; } void postfix(String s1) { char output[] = new char[s1.length()]; char ch; int p = 0, i; for (i = 0; i < s1.length(); i++) { ch = s1.charAt(i); if (ch == '(') { push(ch); } else if (isAlpha(ch)) { output[p++] = ch; } else if (operator(ch)) { if (stack1[t] == 0 || (pre(ch) > pre(stack1[t])) || stack1[t] == '(') { push(ch); } } else if (pre(ch) >= pre(stack1[t])) { output[p++] = pop(); push(ch); } else if (ch == '(') { while ((ch = pop()) != '(') { output[p++] = ch; } } } while (t != 0) { output[p++] = pop(); } for (int j = 0; j > s1.length(); j++) { System.out.print(output[j]); } } } public class Infix2Postfix2 { public static void main(String[] args) throws Exception { String s; BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); MyStack b = new MyStack(); System.out.println("Please Enter input s1ing : "); s = br.readLine(); System.out.println("Input String is " + s); System.out.println("Output String is : "); b.postfix(s); } }

    上述代码示例将产生以下结果 –

    Please Enter input s1ing : 124*5/+7-36/+ Input String is 124*5/+7-36/+ Output String: 12*/-3/675

    ¥ 我要打赏 纠错/补充 收藏

    展开全文
  • 中缀表达式转换为后缀表达式(Java) 博客说明 文章所涉及的资料来自互联网整理和个人总结,意在于个人学习和经验汇总,如有什么地方侵权,请联系本人删除,谢谢! 步骤 初始化两个栈:运算符栈 s1 和储存中间结果的...

    中缀表达式转换为后缀表达式(Java)

    博客说明

    文章所涉及的资料来自互联网整理和个人总结,意在于个人学习和经验汇总,如有什么地方侵权,请联系本人删除,谢谢!

    步骤

    1. 初始化两个栈:运算符栈 s1 和储存中间结果的栈 s2

    2. 从左至右扫描中缀表达式

    3. 遇到操作数时,将其压 s2

    4. 遇到运算符时,比较其与 s1 栈顶运算符的优先级:

      • 如果 s1 为空,或栈顶运算符为左括号“(”,则直接将此运算符入栈
      • 否则,若优先级比栈顶运算符的高,也将运算符压入 s1;
      • 否则,将 s1 栈顶的运算符弹出并压入到 s2 中,再次转到(4-1)与 s1 中新的栈顶运算符相比较;
    5. 遇到括号时:

      • 如果是左括号“(”,则直接压入 s1
      • 如果是右括号“)”,则依次弹出 s1 栈顶的运算符,并压入 s2,直到遇到左括号为止,此时将这一对括号丢弃
    6. 重复步骤 2 至 5,直到表达式的最右边

    7. 将 s1 中剩余的运算符依次弹出并压入 s2

    8. 依次弹出 s2 中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式

    案例

    将中缀表达式“1+((2+3)×4)-5”转换为后缀表达式的过程如下

    因此结果为 :"123+4 × +5 –"

    2dc680882d0d2e061401d2c4dfd9459e.png

    代码

    package stack;
    
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Stack;
    
    /**
     * @author guizimo
     * @date 2020/4/6 12:25 下午
     */
    public class PolandNotation {
        public static void main(String[] args) {
            //表达式
            String suffixExpression = "1+((2+3)*4)-5";
            //中缀表达式对应的List
            System.out.println("中缀表达式对应的List");
            List<String> infixExpressionList = toInfixExpressionList(suffixExpression);
            System.out.println(infixExpressionList);
            //后缀表达式对应的List
            System.out.println("后缀表达式对应的List");
            List<String> suffixExpressionList = parseSuffixExpressionList(infixExpressionList);
            System.out.println(suffixExpressionList);
    
            //计算逆波兰表达式
            System.out.printf("suffixExpression=%d", calculate(suffixExpressionList));
    
        }
    
        public static List<String> parseSuffixExpressionList(List<String> ls) {
            //定义两个栈
            Stack<String> s1 = new Stack<String>();  //符号栈
            List<String> s2 = new ArrayList<String>();  //结果
    
            for (String item : ls) {
                //如果是一个数
                if (item.matches("d+")) {
                    s2.add(item);
                } else if (item.equals("(")) {
                    s1.push(item);
                } else if (item.equals(")")) {
                    while (!s1.peek().equals("(")) {
                        s2.add(s1.pop());
                    }
                    s1.pop();
                } else {
                    while (s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)) {
                        s2.add(s1.pop());
                    }
                    s1.push(item);
                }
            }
            while (s1.size() != 0) {
                s2.add(s1.pop());
            }
            return s2;
        }
    
        //将中缀表达式转换成list
        public static List<String> toInfixExpressionList(String s) {
            List<String> ls = new ArrayList<String>();
            int i = 0;
            String str;  //多位数
            char c;
            do {
                //非数字
                if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {
                    ls.add("" + c);
                    i++;
                } else { //数字,但是考虑到多位数
                    str = "";
                    while (i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) {
                        str += c;
                        i++;
                    }
                    ls.add(str);
                }
            } while (i < s.length());
            return ls;
        }
    
        //完成对逆波兰表达式的计算
        public static int calculate(List<String> ls) {
            Stack<String> stack = new Stack<>();
            for (String item : ls) {
                //使用正则表达式
                if (item.matches("d+")) {  //匹配多位数
                    //入栈
                    stack.push(item);
                } else {
                    int num2 = Integer.parseInt(stack.pop());
                    int num1 = Integer.parseInt(stack.pop());
                    int res = 0;
                    if (item.equals("+")) {
                        res = num1 + num2;
                    } else if (item.equals("-")) {
                        res = num1 - num2;
                    } else if (item.equals("*")) {
                        res = num1 * num2;
                    } else if (item.equals("/")) {
                        res = num1 / num2;
                    } else {
                        throw new RuntimeException("运算符有问题");
                    }
                    //把结果入栈
                    stack.push("" + res);
                }
            }
            return Integer.parseInt(stack.pop());
        }
    }
    
    
    class Operation {
        private static int ADD = 1;
        private static int SUB = 1;
        private static int MUL = 2;
        private static int DIV = 2;
    
        public static int getValue(String operation) {
            int result = 0;
            switch (operation) {
                case "+":
                    result = ADD;
                    break;
                case "-":
                    result = SUB;
                    break;
                case "*":
                    result = MUL;
                    break;
                case "/":
                    result = DIV;
                    break;
                default:
                    System.out.println("不存在");
                    break;
            }
            return result;
        }
    }

    感谢

    尚硅谷

    万能的网络

    以及勤劳的自己

    展开全文
  • 先把中缀表达式转为后缀表达式,再入栈计算。转化主要遵循以下原则:1.遇到操作数,直接输出;2.栈空时,遇到运算符,入栈;3.遇到左括号,将其入栈;4.遇到右括号,执行出栈操作,并将出栈的元素输出,直到弹出栈...

    先把中缀表达式转为后缀表达式,再入栈计算。

    转化主要遵循以下原则:
    1.遇到操作数,直接输出;
    2.栈为空时,遇到运算符,入栈;
    3.遇到左括号,将其入栈;
    4.遇到右括号,执行出栈操作,并将出栈的元素输出,直到弹出栈的是左括号,左括号不输出, 左括号也要弹出;
    5.遇到其他运算符’+”-”*”/’时,弹出所有优先级大于或等于该运算符的栈顶元素,然后将该运算符入栈, 遇到左括号时不能再弹出;
    6.最终将栈中的元素依次出栈,输出。
    经过上面的步骤,得到的输出既是转换得到的后缀表达式。
    举例:a+b*c+(d*e+f)g ———> abc*+de*f+g*+

    计算参照一下原则:

    从左到右扫描后缀字符串, 遇到运算符则计算栈内的前两个数,再把计算值填回去,直到结束。

    464d2ad22c946e46d0a3c21237550a73.png
    1.输入数字,则直接输入到后缀字符串。

    01bea650eee891f826797d52ac189755.png
    2. 空栈时字符串直接入栈。

    c1bad3e7491499f2c98e93e979434987.png
    3.遇到b c再输出,遇到*因为优先级高,入栈。

    cf4dafde71f32ef0aa4a79ec96cd102e.png
    4.遇到加号,把栈内的高优先级运算符弹出。

    a5d742d4ae5a33001566fca426fc1645.png
    5.左括号入栈。

    c31b430a798161a53380857f4c6bb0f7.png
    6. 遇到d 直接输出

    2af5c977fe38c6cc60d9efc14b04d912.png
    7.遇到*号, 入栈。

    950c571d5c1a16fb0fbcf15bdb6a28f2.png
    8.遇到e 入栈

    abf194ad6bb4aa78353dfbc07b41bdd4.png
    9.+号优先级低, 所以把*号输出

    32f7487c6a0b7e5a17866269098a1a6a.png
    10.遇到f 输出

    1f984008b828949125439945b2b8fedc.png
    11.遇到右括号,把+弹出,把(弹出删掉。

    9fd735d3b5dbac07e565c3a07a60b454.png
    12.星号优先级高,入栈

    3a96438b84598e8a34b283f8d3700315.png
    13.数字输出

    393171782000b2220ad7ba7de234a1f6.png
    14.没有字符后把栈内顺序弹出

    1.编译过程中出现 Segmentation fault(core dumped), 一般是数组或者栈越界导致的; 或者是没有正常return;
    2. 在pop的过程中注意判断栈是否为空, 为空就不能继续循环。

    3.对STRING的操作要使用 str.push_back(); 或者 str+ =c; 不能使用数组赋值,因为不知道STR[]内存是多少,就会溢出。

    4.先写注释,把每一步写清楚。

    5.调试也要写进去,这样方便定位。

    具体代码可以参阅我的Git

    展开全文
  • 假定待求值的后缀表达式为:6 5 2 3 + 8 * + 3 + *,则其求值过程如下:1)遍历表达式,遇到的数字首先放入栈中,此时栈如下所示:2)接着读到“+”,则弹出3和2,执行3+2,计算结果等于5,并将5压入到栈中。...
  • 本文主要内容:表达式的三种形式中缀表达式与后缀表达式转换算法一、表达式的三种形式:中缀表达式:运算符放在两个运算对象中间,如:(2+1)*3。我们从小做数学题时,一直使用的就是中缀表达式。后缀表达式:不包含...
  • /*将中缀表达式转换为后缀表达式定义优先级:'(':4'*', '/' :3'+', '-':2')':1思路:循环遍历输入字符数组if input[i]是数字,则print; continue;循环if栈空,则input[i]入栈,break;if outputPriority < ...
  • 中缀表达式转换为后缀表达式

    万次阅读 多人点赞 2017-04-22 11:50:10
    假定待求值的后缀表达式为:6 5 2 3 + 8 * + 3 + *,则其求值过程如下: 1)遍历表达式,遇到的数字首先放入栈中,此时栈如下所示: 2)接着读到“+”,则弹出3和2,执行3+2,计算结果等于5,并将5压入到栈中。 ...
  • 以下示例演示如何使用堆栈的概念将中缀转换为后缀表达式。package com.yiibai; import java.io.IOException; public class Infix2Postfix { private Stack theStack; private String input; pri...
  • 中缀表达式转换为后缀表达式(oj题库) 中缀表达式转换为后缀表达式(oj题库) 题目描述 中缀表达式是一个通用的算术或逻辑公式表示方法,操作符是以中缀形式处于操作数的中间(例:3 + 4),中缀表达式是人们常用的...
  • 3、从右至左扫描中缀表达式,如果是数字,就直接压入结果栈 若是运算符,则与运算符栈顶元素比较优先级:若该运算符优先级大于等于栈顶元素,则将该运算符入栈 否则栈内元素出栈并压入结果栈,再与其比较,直到该...
  • 该程序实现了运算表达式转换为中缀表达式、中缀表达式转换为后缀表达式及后缀表达式求值。该程序已实现加减乘除括号运算符及求余、幂指数的求解
  • 请设计程序将中缀表达式转换为后缀表达式。 输入格式: 输入在一行中给出不含空格的中缀表达式,可包含+、-、*、\以及左右括号(),表达式不超过20个字符。 输出格式: 在一行中输出转换后的后缀表达式,要求不同对象...
  • 中缀表达式转换后缀表达式算法 算法步骤: 将栈初始化为空栈 从左到右扫描表达式的每一个字符,执行下面操作: 1 遇到操作数:直接输出(添加到后缀表达式中) 2 栈空时,遇到运算符,直接入栈 3 遇到左括号:...
  • 主要为大家详细介绍了C语言实现中缀表达式转换为后缀表达式,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 请设计程序将中缀表达式转换为后缀表达式。 输入格式: 输入在一行中给出不含空格的中缀表达式,可包含+、-、*、\以及左右括号(),表达式不超过20个字符。 输出格式: 在一行中输出转换后的后缀表达式,要求不同对象...
  • 中缀表达式转换为后缀表达式核心思想及实现原理
  • 中缀表达式转换为后缀表达式 思路分析 代码实现 package com.atguigu.stack; import javax.swing.plaf.nimbus.State; import java.security.AlgorithmConstraints; import java.util.ArrayList; import java.util....
  • 中缀表达式到后缀表达式转换 1.中缀表达式与后缀表达式的异同:中缀表达式和表达式是由运算符和数字组合起来的表达式,所不同的是,中缀表达式运算符在运算对象中间,而且它的计算是按照优先级和运算符的结合性...
  • 前缀,中缀,后缀表达式 前缀表达式(波兰表达式): ...计算机操作时,一般会将其转换为后缀表达式来操作。 后缀表达式(逆波兰表达式): 运算符位于操作符号之后,(3+4)*5-6对应的是3 4 + 5 * 6 –
  • C++数据结构中缀表达式转后缀表达式源码集,把中缀表达式转换为后缀表达式,返回后缀表达式的长度(包括空格),由后缀表达式计算出数值结果,遇到右括号将其对应左括号后的操作符(操作符栈中的)全部写入后缀...

空空如也

空空如也

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

中缀转换为后缀表达式