[算法 – Java的] 跳转缀表达式后缀 – Java的 – 转换到中缀后缀
代数表达式使用的每一天都作为核心要素 (缀). 这表示是可以理解的,因为人类的大多数运营商 (+, -, *, /) 运营商有两个房子和他们分开两个操作数一起. 然而,对于计算机, 计算这种形式的代数表达式的值不是简单,因为我们还在做. 为了解决这个问题, PC应该切换的元素代数表达式表示成形式作为前缀或后缀.
是怎样的表情前缀, 中缀和后缀
在也许是入门款也想象中的表达如何缀, 这很容易理解运营商将被放置在两个操作数之间, 这当然是双宫. 因此,基于操作者的位置, 我们是否可以以另一种形式进行代数表达式? 答案是, 和作为所述, 因为我们有三个表达式前缀 (字首), 缀 (缀) 和后缀 (后缀). 让我们来看看一点点的介绍表示表达式前缀和后缀,以了解更多关于他们.
– 字首: 表达前缀由设置操作的操作数之前表示. 这表示还名义下“波兰式”由数学家扬卢卡西维奇称为发明波兰一年 1920. 与此表示, 而不是编写X Y二次外形, 我会写 XY. 取决于运营商的优先权,它们将被不同地布置, 你可以看到在这个主人的后面的一些例子.
– 后缀: 相反,前缀的方式, 即运营商将被放置在操作数后. 这种表示被称为“逆波兰式”或简称为RPN (逆波兰式), 发明于十年中期 1950 由哲学家和科学家查尔斯·汉布林澳大利亚计算机.
Một số ví dụ:
从缀表达式为后缀的方法转移
运营商优先
一开始计算前的重要的事情必须是运营商的优先在输入表达式. 为简单起见,我们只考虑二元操作和常用的包括: 乘 (+),减 (-), 乘 (*), 分 (/). 因此运营商“*, /“具有较高的优先级和运算符” , -”. 所以我们采取优先模式如下运营商:
public int priority(char c){ // thiet lap thu tu uu tien if (c == '+' || c == '-') return 1; else if (c == '*' || c == '/') return 2; else return 0; }
检查操作和操作数
在这个转换算法的方法,我们需要检查链条的组件是操作数的运算符或不. 除了使用结构或开关是否冗长,不方便开发时, 我将使用正则表达式来测试.
也因为输入字符串是一个代数表达式, 如果操作数将不仅考虑数量也从az和AZ字母.
有一个规则,使用字母时,只允许只有一个字母代表一个操作数, 使用多个数字即使当可合并成一个位操作数.
public boolean isOperator(char c){ // kiem tra xem co phai toan tu char operator[] = { '+', '-', '*', '/', ')', '(' }; Arrays.sort(operator); if (Arrays.binarySearch(operator, c) > -1) return true; else return false; }
前缀标准化表达转换
这些表达式可以进入中缀多余空格, 文字不匹配,或写错误的语法.
本节你的看法 在Java中规范化字符串
你也需要配对的连续位数 (操作), 运营商杯, 用一个空格彼此分开. 这些元素,我会被称为令牌.
public String[] processString(String sMath){ // xu ly bieu thuc nhap vao thanh cac phan tu String s1 = "", elementMath[] = null; InfixToPostfix IFP = new InfixToPostfix(); sMath = sMath.trim(); sMath = sMath.replaceAll("\\s+"," "); // chuan hoa sMath for (int i=0; i<sMath.length(); i++){ char c = sMath.charAt(i);//sMath.substring(i,1); if (!IFP.isOperator(c)) s1 = s1 + c; else s1 = s1 + " " + c + " "; } s1 = s1.trim(); s1 = s1.replaceAll("\\s+"," "); // chuan hoa s1 elementMath = s1.split(" "); //tach s1 thanh cac phan tu //System.out.println(s1); return elementMath; }
该算法转换一个大胆的表达缀前缀:
阅读缀表达式每个令牌从左至右, 每个令牌,我们执行下列步骤:
– 如果操作数: 对于输出.
– 如果左括号“(“: 进入堆栈
– 如果右括号“)”: 运营商拿出,放在堆输出,直到遇见左括号“(“. (左括号必须取出一叠)
– 如果操作员:
+/只要操作人员在堆栈的顶部是操作员,并具有等于或超过目前的操作者的优先级,操作者把它从堆栈和向输出.
+/把现有的运营商栈
审查所有表情中缀后, 如果堆被抓住令牌元素在那个地方,打开输出.
首席执行官: 我们将移动表情* A * B C((D-E)+˚F)/从格式来格式化摹缀后缀:
安装Java的
public String[] postfix(String[] elementMath){ InfixToPostfix IFP = new InfixToPostfix(); String s1 = "", E[]; Stack <String> S = new Stack <String>(); for (int i=0; i<elementMath.length; i++){ // duyet cac phan tu char c = elementMath[i].charAt(0); // c la ky tu dau tien cua moi phan tu if (!IFP.isOperator(c)) // neu c khong la toan tu s1 = s1 + " " + elementMath[i]; // xuat elem vao s1 else{ // c la toan tu if (c == '(') S.push(elementMath[i]); // c la "(" -> day phan tu vao Stack else{ if (c == ')'){ // c la ")" char c1; //duyet lai cac phan tu trong Stack do{ c1 = S.peek().charAt(0); // c1 la ky tu dau tien cua phan tu if (c1 != '(') s1 = s1 + " " + S.peek(); // trong khi c1 != "(" S.pop(); }while (c1 != '('); } else{ while (!S.isEmpty() && IFP.priority(S.peek().charAt(0)) >= IFP.priority(c)){ // Stack khong rong va trong khi phan tu trong Stack co do uu tien >= phan tu hien tai s1 = s1 + " " + S.peek(); // xuat phan tu trong Stack ra s1 S.pop(); } S.push(elementMath[i]); // dua phan tu hien tai vao Stack } } } } while (!S.isEmpty()){ // Neu Stack con phan tu thi day het vao s1 s1 = s1 + " " + S.peek(); S.pop(); } E = s1.split(" "); // tach s1 thanh cac phan tu return E; }
最后主程序运行:
public static void main(String[] agrs){ String sMath, elementMath[] = null; InfixToPostfix IFP = new InfixToPostfix(); Scanner input = new Scanner(System.in); sMath = input.nextLine(); // nhap bieu thuc elementMath = IFP.processString(sMath); // tach bieu thuc thanh cac phan tu elementMath = IFP.postfix(elementMath); // dua cac phan tu ve dang postfix for (int i=0; i<elementMath.length; i++) // xuat dang postfix System.out.print(elementMath[i] + " "); input.close(); }
检查结果是正确的, 您可以使用在线转换服务 这里 . 该网站也将转换后执行表达式值的计算.
从这里我们可以建立一个办法 计算表达式后缀的价值
中缀到后缀它不工作!
为什么不工作? 请告诉我你的错误!
表达 3+6-(2*3) … 其在行字符错误C = elementMath[在].的charAt(0); 在功能上后缀 … 指数= 0错误, lenght = 0