首页 > 其他分享 >算术表达式的表示法（即求值法）

算术表达式的表示法（即求值法）

时间：2023-09-24 23:56:53浏览次数：32  
标签：运算符 operators 表示法 operator values 求值 expression 表达式

说明

算术表达式的表示法有多种，其中最常见的包括中缀表达法、前缀表达法和后缀表达法。这些表示法用于表示和求解数学表达式，它们在计算机科学和数学领域都有广泛的应用。

中缀表达法、前缀表达法和后缀表达法是操作符的位置来分类的。操作符位于2个操作之间叫中缀表达法，操作符位于2个操作数之前叫前缀表达法。操作符位于2个操作数之后叫后缀表达式法。

  1. 中缀表达法（Infix Notation）： 它将操作符放置在操作数之间。例如，"2 + 3" 或 "(4 * 5) - 6" 都是中缀表达式。中缀表达式通常需要使用运算符优先级和括号来确保正确的计算顺序。

  2. 前缀表达法（Prefix Notation）： 前缀表达法，也叫做波兰表示法（Polish Notation），将操作符放置在操作数之前。例如，"+ 2 3" 或 "- * 4 5 6" 都是前缀表达式。前缀表达式没有歧义，无需括号或运算符优先级，计算顺序由操作符的位置决定。计算前缀表达式通常需要使用栈数据结构来辅助进行。

  3. 后缀表达法（Postfix Notation）： 后缀表达法，也叫做逆波兰表示法（Reverse Polish Notation），将操作符放置在操作数之后。例如，"2 3 +" 或 "4 5 * 6 -" 都是后缀表达式。与前缀表达式类似，后缀表达式也不需要括号或运算符优先级，并且可以通过栈数据结构来轻松计算。

对于这三种表示法，计算机更容易处理前缀和后缀表达式，因为它们没有歧义，计算顺序直接由操作符的位置决定。

中缀表达式需要解析器来处理运算符优先级和括号，以确定正确的计算顺序。因此，通常会将中缀表达式转换为前缀或后缀形式，以便于计算。

转换中缀表达式为前缀或后缀表达式的过程通常涉及到使用栈来跟踪运算符和操作数的顺序，以确保正确的计算顺序。一旦表达式被转换为前缀或后缀形式，就可以使用栈来执行计算。

总之，算术表达式的表示法有多种，每种都有其自身的优点和适用场景。选择适当的表示法取决于具体的计算需求和计算机程序的实现。前缀和后缀表示法通常更适合计算机计算，而中缀表示法更适合人类可读性。

 

中序表示求值法

 1 class InfixExpressionEvaluator:
 2     def __init__(self):
 3         # 此字典定义了运算符及其优先级。优先级用整数表示，优先级越高的运算符值越大。这个字典将在后面的求值过程中用于确定运算符的优先级
 4         self.operators = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}  # 也就说此例只支持加减乘除幂等
 5 
 6     def evaluate(self, expression):
 7         # 计算栈顶上的操作符，结果入值栈
 8         def apply_operator(operators, values):
 9             operator = operators.pop()
10             right = values.pop()
11             left = values.pop()
12             if operator == '+':
13                 values.append(left + right)
14             elif operator == '-':
15                 values.append(left - right)
16             elif operator == '*':
17                 values.append(left * right)
18             elif operator == '/':
19                 if right == 0:
20                     raise ValueError("Division by zero")
21                 values.append(left / right)
22             elif operator == '^':
23                 values.append(left ** right)
24 
25         # 操作符优先权比较
26         def greater_precedence(op1, op2):
27             return self.operators[op1] > self.operators[op2]
28 
29         temp_operators = []
30         values = []
31         tokens = expression.split()
32 
33         for token in tokens:
34             if token.isnumeric():
35                 values.append(float(token))
36             elif token in self.operators:  # 如果是符合并且是计算字符即非括号
37                 # 当前字符不是'c'并且当前字符栈栈顶的权限当于当作字符token
38                 while (temp_operators and temp_operators[-1] != '(' and greater_precedence(temp_operators[-1], token)):
39                     apply_operator(temp_operators, values)  # 因为栈顶字符优先权大，因此先计算栈顶的
40                 temp_operators.append(token)  # 入栈
41             elif token == '(':  # 自己入字符栈
42                 temp_operators.append(token)
43             elif token == ')':  # 如果是')'运算符开始做运算，直到栈顶是'('
44                 while temp_operators[-1] != '(':
45                     apply_operator(temp_operators, values)
46                 temp_operators.pop()  # 删除'('
47 
48         while temp_operators:  # 如果字符栈还有内容就运算
49             apply_operator(temp_operators, values)
50 
51         return values[0]
52 
53 
54 # 使用示例
55 if __name__ == "__main__":
56     infix_expression = "3 + 4 * ( 2 - 1 )"
57     evaluator = InfixExpressionEvaluator()
58     result = evaluator.evaluate(infix_expression)
59     print(f"Result of {infix_expression} is {result}")

输出：

Result of 3 + 4 * ( 2 - 1 ) is 7.0

　　

这段代码实现了一个中缀表达式求值器 InfixExpressionEvaluator，它可以计算包含加法、减法、乘法、除法和幂运算的中缀表达式。下面是对代码的详细解释：

  1. self.operators 字典定义了运算符及其优先级。优先级用整数表示，优先级越高的运算符值越大。这个字典将在后面的求值过程中用于确定运算符的优先级。

  2. evaluate 方法用于计算给定的中缀表达式。这个方法采用一个字符串表达式作为输入。

  3. apply_operator 函数用于执行栈顶的运算符操作。它从 operators 栈中弹出一个运算符，然后从 values 栈中弹出两个操作数，执行相应的运算，并将结果推入 values 栈中。

  4. greater_precedence 函数用于比较两个运算符的优先级。它接受两个运算符作为参数，并根据它们在 self.operators 中的优先级确定它们的相对优先级。

  5. 在 evaluate 方法中，首先初始化了空的 operators 和 values 栈，然后使用 split 方法将输入的表达式分割成标记。

  6. 接下来，代码遍历每个标记，并根据标记的类型执行不同的操作：

    • 如果标记是数字（通过 isnumeric 方法检查），则将其转换为浮点数并推入 values 栈。
    • 如果标记是运算符（存在于 self.operators 中），则需要处理运算符的优先级。在这里，代码使用一个循环来处理具有更高优先级的运算符，将它们从 operators 栈中弹出并执行相应的操作，然后将当前运算符推入 operators 栈中。这确保了正确的运算顺序。
    • 如果标记是左括号 (，则将其推入 operators 栈中。
    • 如果标记是右括号 )，则需要执行与左括号之间的运算。代码在 operators 栈不为空且栈顶元素不是左括号 ( 时，持续弹出运算符并执行操作，直到遇到左括号为止，然后将左括号弹出。

  7. 最后，当所有标记都处理完毕后，可能还会剩余一些运算符在 operators 栈中。代码使用一个循环来弹出这些运算符并执行操作，确保所有运算都被正确计算。

  8. 返回 values 栈中的最终结果，这个结果就是中缀表达式的计算结果。

  9. 在示例部分，创建了一个 InfixExpressionEvaluator 实例，然后对给定的中缀表达式 "3 + 4 * ( 2 - 1 )" 进行求值，并打印出结果。

总之，这段代码演示了如何使用栈来解析和求值中缀表达式，同时考虑了运算符的优先级和括号的影响，以确保正确的计算顺序。

使用内置函数eval实现表达式求值

1 expression = "3 + 4 * ( 2 - 1 )"
2 result = eval(expression)
3 print(result)  # 输出 7

 

 

 

Java语言简单示例：

  1 package org.allen.data.structure.stack;
  2 
  3 /**
  4  * 中序表示法求值
  5  */
  6 
  7 import java.util.Stack;
  8 
  9 public class InfixExpressionEvaluator {
 10 
 11     /**
 12      * 计算表达式的值
 13      * @param expression 表达式
 14      * @return 表达式结果
 15      */
 16     public static double evaluate(String expression) {
 17         // 用于存放操作数（含计算过程中的操作数）
 18         Stack<Double> values = new Stack<>();
 19         // 用于存放运算符合
 20         Stack<Character> operators = new Stack<>();
 21 
 22         for (int i = 0; i < expression.length(); i++) {
 23             char c = expression.charAt(i);
 24             if (Character.isDigit(c)) {
 25                 StringBuilder numBuilder = new StringBuilder();
 26                 while (i < expression.length() && (Character.isDigit(expression.charAt(i)) || expression.charAt(i) == '.')) {
 27                     numBuilder.append(expression.charAt(i));
 28                     i++;
 29                 }
 30                 i--;
 31                 double num = Double.parseDouble(numBuilder.toString());
 32                 values.push(num);
 33             } else if (c == '(') {
 34                 operators.push(c);
 35             } else if (c == ')') {
 36                 while (!operators.isEmpty() && operators.peek() != '(') {
 37                     double b = values.pop();
 38                     double a = values.pop();
 39                     char operator = operators.pop();
 40                     double result = applyOperator(a, b, operator);
 41                     values.push(result);
 42                 }
 43                 operators.pop(); // Pop the '('
 44             } else if (isOperator(c)) {
 45                 // 判断操作符栈顶操作符是否比当前c的优先级大，大的化执行计算operators.peek()只是读取，尚未出栈
 46                 while (!operators.isEmpty() && precedence(operators.peek()) >= precedence(c)) {
 47                     double b = values.pop();
 48                     double a = values.pop();
 49                     char operator = operators.pop();  // 出栈
 50                     double result = applyOperator(a, b, operator);
 51                     values.push(result);
 52                 }
 53                 operators.push(c);
 54             }
 55         }
 56 
 57         while (!operators.isEmpty()) {
 58             double b = values.pop();
 59             double a = values.pop();
 60             char operator = operators.pop();
 61             double result = applyOperator(a, b, operator);
 62             values.push(result);
 63         }
 64 
 65         return values.pop();
 66     }
 67 
 68     /**
 69      * 判断是否是操作符
 70      */
 71     private static boolean isOperator(char c) {
 72         return c == '+' || c == '-' || c == '*' || c == '/';
 73     }
 74 
 75     /**
 76      * 操作符优先级，数字越大优先级越高
 77      */
 78     private static int precedence(char operator) {
 79         if (operator == '+' || operator == '-') {
 80             return 1;
 81         } else if (operator == '*' || operator == '/') {
 82             return 2;
 83         }
 84         return 0;
 85     }
 86 
 87     /**
 88      * 计算
 89      * @param a 左操作数
 90      * @param b 右操作数
 91      * @param operator 操作符
 92      * @return  操作结果
 93      */
 94     private static double applyOperator(double a, double b, char operator) {
 95         switch (operator) {
 96             case '+':
 97                 return a + b;
 98             case '-':
 99                 return a - b;
100             case '*':
101                 return a * b;
102             case '/':
103                 if (b == 0) {
104                     throw new ArithmeticException("Division by zero");
105                 }
106                 return a / b;
107             default:
108                 throw new IllegalArgumentException("Invalid operator: " + operator);
109         }
110     }
111 
112     public static void main(String[] args) {
113         String infixExpression = "3 + (4 * 5 - 2) / 2";
114         double result = evaluate(infixExpression);
115         System.out.println("Result: " + result);
116     }
117 }

输出：

Result: 12.0

　　

javascript简单示例：

 1 function evaluateInfixExpression(expression) {
 2     // 辅助函数：判断运算符的优先级
 3     function getPrecedence(operator) {
 4         if (operator === '+' || operator === '-') return 1;
 5         if (operator === '*' || operator === '/') return 2;
 6         return 0;
 7     }
 8 
 9     // 辅助函数：执行运算
10     function applyOperator(operators, values) {
11         const operator = operators.pop();
12         const right = values.pop();
13         const left = values.pop();
14         switch (operator) {
15             case '+':
16                 values.push(left + right);
17                 break;
18             case '-':
19                 values.push(left - right);
20                 break;
21             case '*':
22                 values.push(left * right);
23                 break;
24             case '/':
25                 values.push(left / right);
26                 break;
27         }
28     }
29 
30     const operators = []; // 运算符栈
31     const values = [];    // 操作数栈
32 
33     for (let i = 0; i < expression.length; i++) {
34         const char = expression[i];
35         if (char === ' ') {
36             continue; // 忽略空格
37         } else if (!isNaN(parseInt(char))) {
38             let num = parseInt(char);
39             // 如果下一个字符也是数字，则将其合并为多位数字
40             while (i + 1 < expression.length && !isNaN(parseInt(expression[i + 1]))) {
41                 num = num * 10 + parseInt(expression[i + 1]);
42                 i++;
43             }
44             values.push(num);
45         } else if (char === '(') {
46             operators.push(char);
47         } else if (char === ')') {
48             // 弹出运算符直到遇到左括号
49             while (operators.length > 0 && operators[operators.length - 1] !== '(') {
50                 applyOperator(operators, values);
51             }
52             operators.pop(); // 弹出左括号
53         } else {
54             // 处理运算符
55             while (
56                 operators.length > 0 &&
57                 getPrecedence(operators[operators.length - 1]) >= getPrecedence(char)
58                 ) {
59                 applyOperator(operators, values);
60             }
61             operators.push(char);
62         }
63     }
64 
65     // 弹出剩余的运算符并执行计算
66     while (operators.length > 0) {
67         applyOperator(operators, values);
68     }
69 
70     // 返回最终结果
71     return values[0];
72 }
73 
74 // 示例
75 console.log(evaluateInfixExpression("2 + 3 * 4")); // 输出 14
76 console.log(evaluateInfixExpression("( 2 + 3 ) * 4")); // 输出 20
77 console.log(evaluateInfixExpression("7 - 3 / ( 2 + 1 )")); // 输出 6

 

标签：运算符,operators,表示法,operator,values,求值,expression,表达式
From： https://www.cnblogs.com/allenxx/p/17716187.html

相关文章

  • Bash-正则表达式
    一.正则表达式与通配符通配符：用来匹配符合条件的文件名（完全匹配），ls、find、cp这些命令不支持正则表达式，所以只能用通配符正则表达式：用来匹配符合条件的字符串（包含匹配），grep、awk、sed等命令支持正则表达式常用通配符：*（任意字符重复任意多次）、？、[]二.基础正则表达式*（匹配前一个......
  • Python 正则表达式
    正则表达式是一个特殊的字符序列，它能帮助你方便的检查一个字符串是否与某种模式匹配。Python自1.5版本起增加了re模块，它提供Perl风格的正则表达式模式。re模块使Python语言拥有全部的正则表达式功能。compile函数根据一个模式字符串和可选的标志参数生成一个正则表达式对象......
  • 在 Shell命令中，通常会使用通配符表达式来匹配一些文件
    #在Shell命令中，通常会使用通配符表达式来匹配一些文件*，?,[]，{}例:字符含义实例匹配0或多个字符a*ba与b之间可以有任意长度的任意字符,也可以一个也没有,如aabcb,axyzb,a012b,ab。?匹配任意一个字符......
  • Rust的语句和表达式
    在Java中经常听到类似赋值语句、lambda表达式的说法，却从来没有在意过所谓的语句和表达式有什么区别，而在实际的使用中，它们好像确实没啥区别，但是在Rust中，语句和表达式就被严格区分开来了，《Rust程序设计语言》中提到Rust的函数体是由一系列语句和一个可选的结尾表达式来构成。Rust......
  • [leetcode] 10. 正则表达式匹配
    10.正则表达式匹配给你一个字符串s和一个字符规律p，请你来实现一个支持'.'和'*'的正则表达式匹配。'.'匹配任意单个字符'*'匹配零个或多个前面的那一个元素所谓匹配，是要涵盖整个字符串s的，而不是部分字符串。示例1：输入：s="aa",p="a"输出：false解释："a"无......
  • 常用正则表达式
    一、校验数字的表达式数字：[1]*$n位的数字：^\d{n}$至少n位的数字：^\d{n,}$m-n位的数字：^\d{m,n}$零和非零开头的数字：^(0|[1-9][0-9]*)$非零开头的最多带两位小数的数字：^([1-9][0-9]*)+(.[0-9]{1,2})?$带1-2位小数的正数或负数：^(-)?\d+(.\d{1,2})$正数、负数、和小数：^(-|+)?\d......
  • EL表达式和JSTL标签库
    什么是EL表达式以及他的作用EL表达式和jsp表达式脚本输出对比a.jsp<%--CreatedbyIntelliJIDEA.User:SWTDate:2023/9/14Time:22:59TochangethistemplateuseFile|Settings|FileTemplates.--%><%@pagecontentType="text/html;charset=UTF-8......
  • 正则表达式
    正则表达式内容介绍1、字符组字符组是用于查找指定的字符，从左往右依次查找。通常来说，字符组中所有查找对象都是或的关系。符号说明[0123456789]匹配0到9任意一个数(全写)[0-9]匹配0到9任意一个数(缩写)[a-z]匹配26个小写英文字母[A-Z]匹配26个大写英文字......
  • 正则表达式知识点总结
    第一部分：正则表达式概念一个函数：re.findall(pattern,string)一些元字符：. * ? + [] () \ ^ $通过()来改变findall的行为 例1： 判断一个手机号码（长度、开头数字为1、只能是数字）importrea=12345678901defcheck_phone(phone):str_ph=str(pho......
  • JDK8新特性之Lambda表达式和四大函数接口
    在Java8中，加入了Lambda（Lambdaexpression），在使用它以前我们先聊聊为什么要加入Lamdba，使用它对于编程上有什么好处 一、Lamdba的作用1.在我们需要把一些功能传递给某些方法时，在Java8以前，我们就需要去写匿名内部类。引入lambda表达式后，你可以在一个类中简便的定义参数和方法，替代大......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99