笙亿网络策划

DSA 表达式解析怎么实现？数据结构与算法详解

约 25 分钟读完 4 阅
文章导读
上一个 测验 下一个 表达式是指在求值时产生一个值的任何单词、单词组或符号。解析表达式意味着根据特定标准分析表达式中的单词或符号。表达式解析是编程语言中用于求值算术和逻辑表达式的术语。
📋 目录
  1. A Infix Notation
  2. B Prefix Notation
  3. C Postfix Notation
  4. D 解析表达式
  5. E 后缀表示法求值算法
  6. F 表达式解析 - 完整实现
  7. G 使用栈进行表达式解析
A A

数据结构中的表达式解析

上一个
测验
下一个

表达式是指在求值时产生一个值的任何单词、单词组或符号。解析表达式意味着根据特定标准分析表达式中的单词或符号。表达式解析是编程语言中用于求值算术和逻辑表达式的术语。

书写算术表达式的书写方式称为notation（记法）。算术表达式可以用三种不同但等价的记法来书写，即不改变表达式的本质或输出的记法。这些记法包括：

  • Infix Notation
  • Prefix (Polish) Notation
  • Postfix (Reverse-Polish) Notation

这些记法的命名基于它们在表达式中使用运算符的方式。我们将在本章中学习这些记法。

Infix Notation

我们使用infix记法书写表达式，例如 a - b + c，其中运算符用于操作数之间。这种记法对人类来说易于阅读、书写和表述，但对计算设备来说却并不友好。处理infix记法的算法可能在时间和空间消耗方面既困难又昂贵。

Prefix Notation

在这种记法中，运算符前置于操作数，即运算符书写在操作数之前。例如，+ab。这等价于其infix记法a + b。Prefix Notation也称为Polish Notation。

Postfix Notation

这种记法风格称为Reversed Polish Notation。在这种记法中，运算符后置于操作数，即运算符书写在操作数之后。例如，ab+。这等价于其infix记法a + b。

下表简要展示了三种记法的区别：

序号 Infix Notation Prefix Notation Postfix Notation
1 a + b + a b a b +
2 (a + b) ∗ c ∗ + a b c a b + c ∗
3 a ∗ (b + c) ∗ a + b c a b c + ∗
4 a / b + c / d + / a b / c d a b / c d / +
5 (a + b) ∗ (c + d) ∗ + a b + c d a b + c d + ∗
6 ((a + b) ∗ c) - d - ∗ + a b c d a b + c ∗ d -

解析表达式

正如我们所讨论的，设计算法或程序来解析中缀表示法并不是一种很有效率的方式。相反，这些中缀表示法首先被转换为后缀表示法或前缀表示法，然后再进行计算。

要解析任何算术表达式，我们还需要考虑运算符的优先级和结合性。

优先级

当一个操作数位于两个不同运算符之间时，哪个运算符先处理该操作数，由运算符相对于其他运算符的优先级决定。例如 −

Operator Precendence

由于乘法运算的优先级高于加法，b * c 将首先被求值。运算符优先级表将在后面提供。

结合性

结合性描述了具有相同优先级的运算符在表达式中出现时的规则。例如，在表达式 a + b − c 中，+ 和 − 具有相同的优先级，那么表达式的哪一部分将首先被求值，由这些运算符的结合性决定。这里，+ 和 − 都是左结合的，因此表达式将被求值为 (a + b) − c。

优先级和结合性决定了表达式的求值顺序。以下是运算符优先级和结合性表（从高到低）−

Sr.No. Operator Precedence Associativity
1 Exponentiation ^ Highest Right Associative
2 Multiplication ( ∗ ) & Division ( / ) Second Highest Left Associative
3 Addition ( + ) & Subtraction ( − ) Lowest Left Associative

上表显示了运算符的默认行为。在表达式求值的任何时刻，都可以通过使用括号来改变顺序。例如 −

In a + b*c，表达式部分 b*c 将首先被求值，因为乘法的优先级高于加法。我们在这里使用括号让 a + b 首先被求值，例如 (a + b)*c。

后缀表示法求值算法

我们现在来看看如何求值后缀表示法的算法 −

步骤 1. 从左到右扫描表达式 
步骤 2. 如果是操作数，则将其压入栈 
步骤 3. 如果是运算符，则从栈中弹出操作数并 
        执行运算 
步骤 4. 将步骤 3 的输出存回栈中 
步骤 5. 扫描表达式直到所有操作数都被消耗 
步骤 6. 弹出栈并执行运算

表达式解析 - 完整实现

以下是在各种编程语言中表达式解析（中缀表达式转换为后缀表达式）的完整实现 −

C C++ Java Python 
#include<stdio.h>
#include<string.h>
#include<ctype.h>
//char stack  // 字符栈
char stack[25]; 
int top = -1; 
void push(char item) {
   stack[++top] = item; 
} 
char pop() {
   return stack[top--]; 
} 
//returns precedence of operators  // 返回运算符的优先级
int precedence(char symbol) {
   switch(symbol) {
      case '+': 
      case '-':
         return 2; 
         break; 
      case '*': 
      case '/':
         return 3; 
         break; 
      case '^': 
         return 4; 
         break; 
      case '(': 
      case ')': 
      case '#':
         return 1; 
         break; 
   } 
} 
//check whether the symbol is operator?  // 检查符号是否为运算符？
int isOperator(char symbol) {

   switch(symbol) {
      case '+': 
      case '-': 
      case '*': 
      case '/': 
      case '^': 
      case '(': 
      case ')':
         return 1; 
      break; 
         default:
         return 0; 
   } 
} 

//converts infix expression to postfix  // 将中缀表达式转换为后缀表达式
void convert(char infix[],char postfix[]) {
   int i,symbol,j = 0; 
   stack[++top] = '#'; 
	
   for(i = 0;i<strlen(infix);i++) {
      symbol = infix[i]; 
		
      if(isOperator(symbol) == 0) {
         postfix[j] = symbol; 
         j++; 
      } else {
         if(symbol == '(') {
            push(symbol); 
         } else {
            if(symbol == ')') {
				
               while(stack[top] != '(') {
                  postfix[j] = pop(); 
                  j++; 
               } 
					
               pop();   //pop out (.  // 弹出 '('
            } else {
               if(precedence(symbol)>precedence(stack[top])) {
                  push(symbol); 
               } else {
					
                  while(precedence(symbol)<=precedence(stack[top])) {
                     postfix[j] = pop(); 
                     j++; 
                  } 
						
                  push(symbol); 
               }
            }
         }
      }
   }
	
   while(stack[top] != '#') {
      postfix[j] = pop(); 
      j++; 
   } 
	
   postfix[j]='\0';  //null terminate string.  // 字符串以空字符结尾
} 

//int stack  // 整数栈
int stack_int[25]; 
int top_int = -1; 

void push_int(int item) {
   stack_int[++top_int] = item; 
} 

char pop_int() {
   return stack_int[top_int--]; 
} 

//evaluates postfix expression  // 计算后缀表达式
int evaluate(char *postfix){

   char ch;
   int i = 0,operand1,operand2;

   while( (ch = postfix[i++]) != '\0') {
	
      if(isdigit(ch)) {
         push_int(ch-'0');  // Push the operand  // 压入操作数
      } else {
         //Operator,pop two  operands  // 运算符，弹出两个操作数
         operand2 = pop_int();
         operand1 = pop_int();
			
         switch(ch) {
            case '+':
               push_int(operand1+operand2);
               break;
            case '-':
               push_int(operand1-operand2);
               break;
            case '*':
               push_int(operand1*operand2);
               break;
            case '/':
               push_int(operand1/operand2);
               break;
         }
      }
   }
	
   return stack_int[top_int];
}

void main() { 
   char infix[25] = "1*(2+3)",postfix[25]; 
   convert(infix,postfix); 
	
   printf("Infix expression is: %s\n" , infix);
   printf("Postfix expression is: %s\n" , postfix);
   printf("Evaluated expression is: %d\n" , evaluate(postfix));
}

输出

Infix expression is: 1*(2+3)
Postfix expression is: 123+*
Evaluated expression is: 5 

// C++ Code for Expression Parsing Using Stack  // 使用栈进行表达式解析的 C++ 代码
#include <iostream>
#include <string>
#include <cctype>
#include <stack>
// char stack  // 字符栈
std::stack<char> stack;

void push(char item) {
    stack.push(item);
}
char pop() {
    char top = stack.top();
    stack.pop();
    return top;
}
// returns precedence of operators  // 返回运算符的优先级
int precedence(char symbol) {
    switch(symbol) {
        case '+':
        case '-':
            return 2;
        case '*':
        case '/':
            return 3;
        case '^':
            return 4;
        case '(':
        case ')':
        case '#':
            return 1;
    }
    return 0;
}
// check whether the symbol is an operator  // 检查符号是否为运算符
int isOperator(char symbol) {
    switch(symbol) {
        case '+':
        case '-':
        case '*':
        case '/':
        case '^':
        case '(':
        case ')':
            return 1;
        default:
            return 0;
    }
}
// converts infix expression to postfix  // 将中缀表达式转换为后缀表达式
void convert(const std::string& infix, std::string& postfix) {
    int j = 0;
    stack.push('#');
    for (char symbol : infix) {
        if (isOperator(symbol) == 0) {
            postfix += symbol;
            j++;
        } else {
            if (symbol == '(') {
                push(symbol);
            } else {
                if (symbol == ')') {
                    while (stack.top() != '(') {
                        postfix += pop();
                        j++;
                    }
                    stack.pop(); // pop out '('  // 弹出 '('
                } else {
                    if (precedence(symbol) > precedence(stack.top())) {
                        push(symbol);
                    } else {
                        while (precedence(symbol) <= precedence(stack.top())) {
                            postfix += pop();
                            j++;
                        }
                        push(symbol);
                    }
                }
            }
        }
    }

    while (stack.top() != '#') {
        postfix += pop();
        j++;
    }

    postfix[j] = '\0'; // null terminate string  // 字符串以空字符结尾
}
// evaluates postfix expression  // 计算后缀表达式
int evaluate(const std::string& postfix) {
    std::stack<int> stack_int;
    int operand1, operand2;
    for (char ch : postfix) {
        if (std::isdigit(ch)) {
            stack_int.push(ch - '0'); // Push the operand  // 压入操作数
        } else {
            // Operator, pop two operands  // 运算符，弹出两个操作数
            operand2 = stack_int.top();
            stack_int.pop();
            operand1 = stack_int.top();
            stack_int.pop();
            switch (ch) {
                case '+':
                    stack_int.push(operand1 + operand2);
                    break;
                case '-':
                    stack_int.push(operand1 - operand2);
                    break;
                case '*':
                    stack_int.push(operand1 * operand2);
                    break;
                case '/':
                    stack_int.push(operand1 / operand2);
                    break;
            }
        }
    }
    return stack_int.top();
}
int main() {
    std::string infix = "1*(2+3)", postfix;
    convert(infix, postfix);
    std::cout << "Infix expression is: " << infix << std::endl;
    std::cout << "Postfix expression is: " << postfix << std::endl;
    std::cout << "Evaluated expression is: " << evaluate(postfix) << std::endl;
    return 0;
}

输出

Infix expression is: 1*(2+3)
Postfix expression is: 123+*
Evaluated expression is: 5

// Java Code for Expression Parsing Using Stack  // 使用栈进行表达式解析的 Java 代码
import java.util.Stack;
public class Main {
    // char stack  // 字符栈
    static Stack<Character> stack = new Stack<>();
    static void push(char item) {
        stack.push(item);
    }
    static char pop() {
        return stack.pop();
    }
    // returns precedence of operators  // 返回运算符的优先级
    static int precedence(char symbol) {
        switch (symbol) {
            case '+':
            case '-':
                return 2;
            case '*':
            case '/':
                return 3;
            case '^':
                return 4;
            case '(':
            case ')':
            case '#':
                return 1;
        }
        return 0;
    }
    // check whether the symbol is an operator  // 检查符号是否为运算符
    static int isOperator(char symbol) {
        switch (symbol) {
            case '+':
            case '-':
            case '*':
            case '/':
            case '^':
            case '(':
            case ')':
                return 1;
            default:
                return 0;
        }
    }
    // converts infix expression to postfix  // 将中缀表达式转换为后缀表达式
    static void convert(String infix, StringBuilder postfix) {
        int j = 0;
        stack.push('#');
        for (char symbol : infix.toCharArray()) {
            if (isOperator(symbol) == 0) {
                postfix.append(symbol);
                j++;
            } else {
                if (symbol == '(') {
                    push(symbol);
                } else {
                    if (symbol == ')') {
                        while (stack.peek() != '(') {
                            postfix.append(pop());
                            j++;
                        }
                        stack.pop(); // pop out '('  // 弹出 '('
                    } else {
                        if (precedence(symbol) > precedence(stack.peek())) {
                            push(symbol);
                        } else {
                            while (precedence(symbol) <= precedence(stack.peek())) {
                                postfix.append(pop());
                                j++;
                            }
                            push(symbol);
                        }
                    }
                }
            }
        }
        while (stack.peek() != '#') {
            postfix.append(pop());
            j++;
        }
    }
    // evaluates postfix expression  // 计算后缀表达式
    static int evaluate(String postfix) {
        Stack<Integer> stackInt = new Stack<>();
        int operand1, operand2;
        for (char ch : postfix.toCharArray()) {
            if (Character.isDigit(ch)) {
                stackInt.push(ch - '0'); // Push the operand  // 压入操作数
            } else {
                // Operator, pop two operands  // 运算符，弹出两个操作数
                operand2 = stackInt.pop();
                operand1 = stackInt.pop();
                switch (ch) {
                    case '+':
                        stackInt.push(operand1 + operand2);
                        break;
                    case '-':
                        stackInt.push(operand1 - operand2);
                        break;
                    case '*':
                        stackInt.push(operand1 * operand2);
                        break;
                    case '/':
                        stackInt.push(operand1 / operand2);
                        break;
                }
            }
        }
        return stackInt.peek();
    }
    public static void main(String[] args) {
        String infix = "1*(2+3)";
        StringBuilder postfix = new StringBuilder();
        convert(infix, postfix);
        System.out.println("Infix expression is: " + infix);
        System.out.println("Postfix expression is: " + postfix);
        System.out.println("Evaluated expression is: " + evaluate(postfix.toString()));
    }
}

输出

Infix expression is: 1*(2+3)
Postfix expression is: 123+*
Evaluated expression is: 5

class Main:
    stack = []
    @staticmethod
    def push(item):
        Main.stack.append(item)
    @staticmethod
    def pop():
        return Main.stack.pop()
    #returns precedence of operators  # 返回运算符的优先级
    @staticmethod
    def precedence(symbol):
        if symbol in ['+', '-']:
            return 2
        elif symbol in ['*', '/']:
            return 3
        elif symbol == '^':
            return 4
        elif symbol in ['(', ')', '#']:
            return 1
        return 0
    #check whether the symbol is an operator  # 检查符号是否为运算符
    @staticmethod
    def is_operator(symbol):
        return symbol in ['+', '-', '*', '/', '^', '(', ')']
    @staticmethod
    def convert(infix):
        postfix = ""
        j = 0
        Main.push('#')
        for symbol in infix:
            if not Main.is_operator(symbol):
                postfix += symbol
                j += 1
            else:
                if symbol == '(':
                    Main.push(symbol)
                else:
                    if symbol == ')':
                        while Main.stack[-1] != '(':
                            postfix += Main.pop()
                            j += 1
                        Main.pop()  # pop out '('  # 弹出 '('
                    else:
                        if Main.precedence(symbol) > Main.precedence(Main.stack[-1]):
                            Main.push(symbol)
                        else:
                            while Main.precedence(symbol) <= Main.precedence(Main.stack[-1]):
                                postfix += Main.pop()
                                j += 1
                            Main.push(symbol)
        while Main.stack[-1] != '#':
            postfix += Main.pop()
            j += 1
        return postfix
    @staticmethod
    def evaluate(postfix):
        stack_int = []
        for ch in postfix:
            if ch.isdigit():
                stack_int.append(int(ch))
            else:
                operand2 = stack_int.pop()
                operand1 = stack_int.pop()
                if ch == '+':
                    stack_int.append(operand1 + operand2)
                elif ch == '-':
                    stack_int.append(operand1 - operand2)
                elif ch == '*':
                    stack_int.append(operand1 * operand2)
                elif ch == '/':
                    stack_int.append(operand1 / operand2)
        return stack_int[0]
    @staticmethod
    def main():
        infix = "1*(2+3)"
        postfix = Main.convert(infix)
        print("Infix expression is:", infix)
        print("Postfix expression is:", postfix)
        print("Evaluated expression is:", Main.evaluate(postfix))
Main.main()

输出

Infix expression is: 1*(2+3)
Postfix expression is: 123+*
Evaluated expression is: 5

使用栈进行表达式解析

我们可以使用不同的数据结构来实现表达式解析。请查看使用 Stack 进行表达式解析的实现