网站程序代码优化,android安装教程,广告设计与制作专业简历,互联网基础知识入门后缀表达式的计算机求值
计算规则
从左至右扫描表达式#xff0c;遇到数字时#xff0c;将数字压入堆栈#xff0c;遇到运算符时#xff0c;弹出栈顶的两个数#xff0c;用运算符对它们做相应的计算#xff08;次顶元素 和 栈顶元素#xff09;#xff0c;并将结果入…后缀表达式的计算机求值
计算规则
从左至右扫描表达式遇到数字时将数字压入堆栈遇到运算符时弹出栈顶的两个数用运算符对它们做相应的计算次顶元素 和 栈顶元素并将结果入栈重复上述过程直到表达式最右端最后运算得出的值即为表达式的结果。
举例分析
例如: (34)*5-6 对应的后缀表达式就是 3 4 5 * 6 - , 针对后缀表达式求值步骤如下:
从左至右扫描将3和4压入堆栈遇到运算符因此弹出4和34为栈顶元素3为次顶元素计算出34的值得7再将7入栈将5入栈接下来是*运算符因此弹出5和7计算出7*535将35入栈将6入栈最后是-运算符计算出35-6的值即29由此得出最终结果
扫描元素s1(栈底-栈顶说明33数字入栈43 4数字入栈7运算符弹出栈顶的两个数用运算符对它们做相应的计算顺序次顶元素 和 栈顶元素并将结果入栈57 5数字入栈*35运算符弹出栈顶的两个数用运算符对它们做相应的计算顺序次顶元素 和 栈顶元素并将结果入栈635 6数字入栈-29运算符弹出栈顶的两个数用运算符对它们做相应的计算顺序次顶元素 和 栈顶元素并将结果入栈29最终结果保存在操作数栈中
代码实现
import java.util.Stack;/*** Author: * Create: 2024-10-01 10:36* Description:* (34)×5-6 -- 3 4 5 × 6 -*/
public class 后缀表达式 {public static void main(String[] args) {String expression 3 4 5 * 6 - ;String[] str expression.split( );StackInteger numStack new Stack();int res 0;for (String s : str) {if (s.matches(\\d)) {numStack.push(Integer.parseInt(s));} else {Integer num1 numStack.pop();Integer num2 numStack.pop();switch (s) {case :res num2 num1;break;case -:res num2 - num1;break;case *:res num2 * num1;break;case /:res num2 / num1;break;default:throw new ArithmeticException(运算符有误);}numStack.push(res);}}System.out.println(res);}
}逆波兰计算器
逆波兰表达式(后缀表达式)支持小括号和多位数整数计算后缀表达式适合计算机进行运算但是人却不太容易写出来尤其是表达式很长的情况下因此在开发中我们需要将中缀表达式转成后缀表达式。
中缀表达式转后缀表达式规则
具体步骤如下:
初始化两个栈存储中间结果的栈s1和运算符栈s2定义-优先级为1*/优先级为2其他0从左至右扫描中缀表达式遇到操作数时将其压s1遇到运算符时比较其与s2栈顶运算符的优先级 如果s2不为空 优先级栈顶运算符优先级的定义判定了栈顶运算符为左括号“(”的情况所以不用在考虑遇到做括号的情况将s2栈顶的运算符弹出并压入到s1中循环判断再次转到(4-1)与s2中新的栈顶运算符相比较出了循环将运算符压入s2遇到括号时 如果是左括号“(”则直接压入s2如果是右括号“)”则依次弹出s2栈顶的运算符并压入s1直到遇到左括号为止此时将这一对括号丢弃重复步骤3至5直到表达式的最右边将s2中剩余的运算符依次弹出并压入s1依次弹出s1中的元素并输出结果的逆序即为中缀表达式对应的后缀表达式
举例分析
将中缀表达式 “1((23)*4)-5” 转换为后缀表达式 1 2 3 4 * 5 – 的过程如下
扫描元素s1(栈底-栈顶s2(栈底-栈顶说明11 操作数直接入栈s11s2为空入栈s2(1 (左括号直接入栈s2(1 ( ( 左括号直接入栈s221 2 ( ( 操作数直接入栈s11 2 ( ( s2栈顶运算符为左括号入栈s231 2 3 ( ( 操作数直接入栈s1)1 2 3 ( 右括号依次弹出s2栈顶的运算符压入s1直到遇到左括号为止此时将这一对括号丢弃*1 2 3 ( *s2栈顶运算符为左括号入栈s241 2 3 4 ( *操作数直接入栈s1)1 2 3 4 *右括号依次弹出s2栈顶的运算符压入s1直到遇到左括号为止此时将这一对括号丢弃-1 2 3 4 * --优先级不比高将弹出并压入到s1中此时s2为空-入栈s251 2 3 4 * 5-操作数直接入栈s11 2 3 4 * 5 -s2中剩余的运算符依次弹出并压入s1结果为s1出栈的逆序
代码实现
import java.util.ArrayList;
import java.util.Stack;/*** Author: * Create: 2024-10-01 11:58* Description: 1((23)*4)-5 -- 1 2 3 4 * 5 –*/
public class 中缀转后缀 {public static void main(String[] args) {String infix 1((23)*4)-5;ArrayListString suffixList new ArrayList();StackString oper new Stack();int len infix.length();for (int i 0; i len; i) {char c infix.charAt(i);if (Character.isDigit(c)) {int j i;while (j len Character.isDigit(infix.charAt(j))) {j;}suffixList.add(infix.substring(i, j));i j - 1;} else if (c () {oper.push(c );} else if (c )) {while (!oper.isEmpty() !oper.peek().equals(()) {suffixList.add(oper.pop());}oper.pop(); // 弹出左括号} else { // 运算符while (!oper.isEmpty() getPriority(c ) getPriority(oper.peek())) {suffixList.add(oper.pop());}oper.push(c );}}// 弹出剩下运算符while (!oper.isEmpty()) {suffixList.add(oper.pop());}System.out.println(suffixList);}private static int getPriority(String operator) {if (*.equals(operator) || /.equals(operator)) return 2;else if (.equals(operator) || -.equals(operator)) return 1;else return 0;}
}逆波兰计算器代码实现
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;/*** Author: * Create: 2024-10-01 13:51* Description:*/
public class 逆波兰计算器 {public static void main(String[] args) {Scanner in new Scanner(System.in);String infix in.nextLine().replace( , );// 转化后缀表达式ListString suffix changeToSuffix(infix);// 计算后缀表达式int res calculateSuffix(suffix);System.out.println(res);}private static int calculateSuffix(ListString suffix) {StackInteger nums new Stack();int res 0;for (String s : suffix) {if (s.matches(\\d)) {nums.push(Integer.parseInt(s));} else {Integer num1 nums.pop();Integer num2 nums.pop();switch (s) {case *:res num2 * num1;break;case /:res num2 / num1;break;case :res num2 num1;break;case -:res num2 - num1;break;default:throw new ArithmeticException(运算符有误);}nums.push(res);}}return res;}private static ListString changeToSuffix(String infix) {StackString oper new Stack();ArrayListString res new ArrayList();int len infix.length();for (int i 0; i len; i) {char c infix.charAt(i);if (Character.isDigit(c)) {int j i;while (j len Character.isDigit(infix.charAt(j))) {j;}res.add(infix.substring(i, j));i --j;} else if (c () {oper.push(c );} else if (c )) {while (!oper.isEmpty() !(.equals(oper.peek())) {res.add(oper.pop());}oper.pop();} else {while (!oper.isEmpty() getPriority(c ) getPriority(oper.peek())) {res.add(oper.pop());}oper.push(c );}}while (!oper.isEmpty()) {res.add(oper.pop());}return res;}private static int getPriority(String operator) {if (*.equals(operator) || /.equals(operator)) return 2;else if (.equals(operator) || -.equals(operator)) return 1;else return 0;}
}
