首页 > 代码库 > 算法(Algorithms)第4版 练习 1.3.9
算法(Algorithms)第4版 练习 1.3.9
主要思路:
用Dijkstra的双栈算法。
遇到数字则压入数字栈中(String)。
遇到运算符则压入运算符栈中(String)。
遇到右括号时,从数字栈和运算法栈中弹出相应的元素,生成相应的运算表达式(添加左括号)。
再次压入数字栈中(String)。
最后从数字栈中弹出最终的运算表达式。
方法实现:
//1.3.9 //only support +-*/ sqrt operator package com.qiusongde; import edu.princeton.cs.algs4.StdIn; import edu.princeton.cs.algs4.StdOut; public class AddLeftParentheses { public static void main(String[] args) { Stack<String> ops = new Stack<String>(); Stack<String> vals = new Stack<String>(); while(!StdIn.isEmpty()) { String s = StdIn.readString(); if(s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/") || s.equals("sqrt")) { ops.push(s); } else if(s.equals(")")) { String op = ops.pop();//operator String v = vals.pop();//value if(op.equals("+") || op.equals("-") || op.equals("*") || op.equals("/")) { String subexpression = "( " + vals.pop() + " " + op + " " + v + " )"; vals.push(subexpression); } if(op.equals("sqrt")) { String subexpression = op + " ( " + v + " )"; vals.push(subexpression); } } else { vals.push(s); } } StdOut.println(vals.pop()); } }
测试结果:
算法(Algorithms)第4版 练习 1.3.9
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。