数据结构中的表达式解析

更新于 2025/10/16 16:21:06

表达式是指任何在求值时生成值的单词、单词组或符号。解析表达式是指根据特定条件分析表达式中的单词或符号。表达式解析是编程语言中用于计算算术和逻辑表达式的值的术语。

算术表达式的书写方式称为表示法。算术表达式可以用三种不同但等效的表示法书写，即不改变表达式的本质或输出。这些表示法分别是 −

中缀表示法
前缀（波兰语）表示法
后缀（逆波兰语）表示法

这些表示法根据它们在表达式中使用运算符的方式命名。在本章中，我们将学习相同的内容。

中缀表示法

我们用中缀表示法书写表达式，例如 a - b + c，其中运算符用在操作数之间。对于我们人类来说，用中缀表示法阅读、书写和说话很容易，但计算设备却不太方便。处理中缀表示法的算法可能很困难，并且在时间和空间消耗方面成本高昂。

前缀表示法

在这种表示法中，运算符前缀在操作数之前，即将运算符写在操作数之前。例如，+ab。这等同于其中缀表示法a + b。前缀表示法也称为波兰表示法。

后缀表示法

这种表示法称为逆波兰表示法。在这种表示法中，运算符被后缀到操作数，即运算符写在操作数之后。例如，ab+。这相当于其中缀表示法a+b。

下表简要展示了这三种表示法的区别。

序号	中缀表示法	前缀表示法	后缀表示法
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 -

解析表达式

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

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

优先级

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

由于乘法运算的优先级高于加法，因此将首先计算 b * c。稍后将提供运算符优先级表。

结合性

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

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

序号	运算符	优先级	结合律
1	幂运算 ^	最高位	右结合律
2	乘法 ( ∗ ) & 除法 ( / )	次最高位	左结合律
3	加法 ( + ) &减法 ( − )	最低	左结合

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

在 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--]; 
} 
//返回运算符的优先级
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; 
   } 
} 
//检查符号是否为运算符？
int isOperator(char symbol) {

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

//将中缀表达式转换为后缀表达式
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';  //空终止字符串. 
} 

//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--]; 
} 

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

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

   while( (ch = postfix[i++]) != '\0') {
	
      if(isdigit(ch)) {
         push_int(ch-'0');  // 将操作数推送至 
      } else {
         //运算符，弹出两个操作数 
         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
" , infix);
   printf("Postfix expression is: %s
" , postfix);
   printf("Evaluated expression is: %d
" , evaluate(postfix));
}

输出

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

// 使用堆栈进行表达式解析的 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;
}
// 返回运算符的优先级
int precedence(char symbol) {
    switch(symbol) {
        case '+':
        case '-':
            return 2;
        case '*':
        case '/':
            return 3;
        case '^':
            return 4;
        case '(':
        case ')':
        case '#':
            return 1;
    }
    return 0;
}
// 检查符号是否为运算符
int isOperator(char symbol) {
    switch(symbol) {
        case '+':
        case '-':
        case '*':
        case '/':
        case '^':
        case '(':
        case ')':
            return 1;
        default:
            return 0;
    }
}
// 将中缀表达式转换为后缀表达式
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'; // 空终止字符串
}
// 计算后缀表达式
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'); // 将操作数推送至
        } else {
            // 运算符，弹出两个操作数
            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 代码
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();
    }
    // 返回运算符的优先级
    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;
    }
    // 检查符号是否为运算符
    static int isOperator(char symbol) {
        switch (symbol) {
            case '+':
            case '-':
            case '*':
            case '/':
            case '^':
            case '(':
            case ')':
                return 1;
            default:
                return 0;
        }
    }
    // 将中缀表达式转换为后缀表达式
    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++;
        }
    }
    // 计算后缀表达式
    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'); // 将操作数推送至
            } else {
                // 运算符，弹出两个操作数
                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()
    #返回运算符的优先级
    @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
    #检查符号是否为运算符
    @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

使用堆栈进行表达式解析

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

的实现。

数据结构和算法

数据结构

链接列表

堆栈 &队列

搜索算法

排序算法

图形数据结构

树数据结构

递归

分而治之

贪婪算法

动态规划

近似算法

随机算法

DSA 有用资源

数据结构中的表达式解析

中缀表示法

前缀表示法

后缀表示法

解析表达式

优先级

结合性

后缀求值算法

表达式解析 - 完整实现

输出

输出

输出

输出

使用堆栈进行表达式解析

颜色选择器

读后有收获微信请站长喝咖啡

错误报告

您的建议:

感谢您的帮助！