数据结构中的表达式解析

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

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

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

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

中缀表示法

我们用中缀表示法编写表达式，例如 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 中，+ 和 - 具有相同的优先级，那么表达式中哪一部分将首先计算，这取决于这些运算符的结合性。在这里，+ 和 - 都是左结合的，因此表达式将计算为(a + b) - c。

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

序号	运算符	优先级	结合性
1	指数 ^	最高	右结合
2	乘法 (∗) & 除法 (/)	次高	左结合
3	加法 (+) & 减法 (-)	最低	左结合

上表显示了运算符的默认行为。在表达式计算的任何时间点，都可以通过使用括号来更改顺序。例如：

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

后缀表达式求值算法

我们现在来看看如何计算后缀表示法的算法：

Step 1. Scan the expression from left to right 
Step 2. If it is an operand push it to stack 
Step 3. If it is an operator pull operand from stack and 
        perform operation 
Step 4. Store the output of step 3, back to stack 
Step 5. Scan the expression until all operands are consumed 
Step 6. Pop the stack and perform operation

表达式解析 - 完整实现

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

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
#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
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

使用栈进行表达式解析

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

打印页面