说明
算术表达式的表示法有多种，其中最常见的包括中缀表达法、前缀表达法和后缀表达法。这些表示法用于表示和求解数学表达式，它们在计算机科学和数学领域都有广泛的应用。
中缀表达法、前缀表达法和后缀表达法是操作符的位置来分类的。操作符位于2个操作之间叫中缀表达法，操作符位于2个操作数之前叫前缀表达法。操作符位于2个操作数之后叫后缀表达式法。
-
中缀表达法（Infix Notation）： 它将操作符放置在操作数之间。例如，"2 + 3" 或 "(4 * 5) - 6" 都是中缀表达式。中缀表达式通常需要使用运算符优先级和括号来确保正确的计算顺序。
-
前缀表达法（Prefix Notation）： 前缀表达法，也叫做波兰表示法（Polish Notation），将操作符放置在操作数之前。例如，"+ 2 3" 或 "- * 4 5 6" 都是前缀表达式。前缀表达式没有歧义，无需括号或运算符优先级，计算顺序由操作符的位置决定。计算前缀表达式通常需要使用栈数据结构来辅助进行。
-
后缀表达法（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，它可以计算包含加法、减法、乘法、除法和幂运算的中缀表达式。下面是对代码的详细解释：
-
self.operators字典定义了运算符及其优先级。优先级用整数表示，优先级越高的运算符值越大。这个字典将在后面的求值过程中用于确定运算符的优先级。 -
evaluate方法用于计算给定的中缀表达式。这个方法采用一个字符串表达式作为输入。 -
apply_operator函数用于执行栈顶的运算符操作。它从operators栈中弹出一个运算符，然后从values栈中弹出两个操作数，执行相应的运算，并将结果推入values栈中。 -
greater_precedence函数用于比较两个运算符的优先级。它接受两个运算符作为参数，并根据它们在self.operators中的优先级确定它们的相对优先级。 -
在
evaluate方法中，首先初始化了空的operators和values栈，然后使用split方法将输入的表达式分割成标记。 -
接下来，代码遍历每个标记，并根据标记的类型执行不同的操作：
- 如果标记是数字（通过
isnumeric方法检查），则将其转换为浮点数并推入values栈。 - 如果标记是运算符（存在于
self.operators中），则需要处理运算符的优先级。在这里，代码使用一个循环来处理具有更高优先级的运算符，将它们从operators栈中弹出并执行相应的操作，然后将当前运算符推入operators栈中。这确保了正确的运算顺序。 - 如果标记是左括号
(，则将其推入operators栈中。 - 如果标记是右括号
)，则需要执行与左括号之间的运算。代码在operators栈不为空且栈顶元素不是左括号(时，持续弹出运算符并执行操作，直到遇到左括号为止，然后将左括号弹出。
- 如果标记是数字（通过
-
最后，当所有标记都处理完毕后，可能还会剩余一些运算符在
operators栈中。代码使用一个循环来弹出这些运算符并执行操作，确保所有运算都被正确计算。 -
返回
values栈中的最终结果，这个结果就是中缀表达式的计算结果。 -
在示例部分，创建了一个
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