数据结构&算法 表达式解析



  • 表达式解析

    编写算术表达式的方法称为符号。算术表达式可以用三种不同但等效的符号表示,即,无需更改表达式的本质或输出。这些符号是-
    • 中缀表示
    • 前缀(波兰语)表示法
    • 后缀(反向波兰语)表示法
    这些符号被命名为它们如何在表达式中使用运算符。在本章中,我们将学习相同的内容。
  • 中缀符号

    我们用中缀表示法编写表达式,例如a -b + c,其中运算符在操作数之间使用。对我们人类来说,用中缀符号读、写和说很容易,但对计算设备来说就不那么容易了。处理中缀表示法的算法在时间和空间消耗方面可能是困难和昂贵的。
  • 前缀表示法

    这种表示法样式称为反向波兰表示法。在这种表示方式中,将运算符后缀到操作数上,即,将运算符写在操作数之后。例如,ab + 。这等效于其后缀符号a + b。
  • 后缀表示法

    在这种表示法中,运算符被前缀为操作数,即运算符被写在操作数之前。例如,+ ab。这等效于其后缀符号a + b。前缀符号也称为波兰符号。
    下表简要尝试显示所有三种表示法的区别-
    中缀 前缀 后缀
    a + b + a b a b +
    (a + b) ∗ c ∗ + a b c a b + c ∗
    a ∗ (b + c) ∗ a + b c a b c + ∗
    a / b + c / d + / a b / c d a b / c d / +
    (a + b) ∗ (c + d) ∗ + a b + c d a b + c d + ∗
    ((a + b) ∗ c) - d - ∗ + a b c d a b + c ∗ d -
  • 解析表达式

    正如我们已经讨论的那样,这不是一种设计算法或程序来解析中缀符号的非常有效的方法。而是将这些中缀表示法首先转换为后缀或前缀表示法,然后进行计算。要解析任何算术表达式,我们还需要注意运算符的优先级和关联性。
    优先顺序
    当一个操作数位于两个不同的运算符之间时,哪个运算符将最先采用该操作数,取决于一个运算符的优先级。例如-
    operator
    由于乘法运算优先于加法运算,因此将首先评估b * c。稍后提供运算符优先级表。
    关联性
    关联性描述了规则,其中具有相同优先级的运算符出现在表达式中。例如,在表达式a + b - c中,+和–都具有相同的优先级,然后表达式的哪一部分将首先被求值,取决于这些算符的关联性。在这里,+和-都保持关联,因此表达式将被评估为(a + b)-c。
    优先级和关联性确定表达式的求值顺序。以下是运算符优先级和关联性表(从最高到最低)-
    操作符 优先级 关联性
    求幂^ 最高 右联想
    乘法(∗)和除法(/) 第二高 左联想
    加法(+)和减法(-) 最低 左联想
    上表显示了运算符的默认行为。在表达式评估的任何时间点,都可以使用括号来更改顺序。例如- 在a + b * c中,将首先对表达式部分b * c进行求值,并将乘法优先于加法。我们在这里使用括号将a + b首先评估,例如(a + b)* c。
  • 后缀评估算法

    现在,我们将研究有关如何评估后缀表示法的算法-
    
    Step 1 − 从左到右扫描表达式
    Step 2 − 如果它是一个操作数,则将其推入堆栈
    Step 3 − 如果它是一个操作符,从堆栈中取出操作数并执行操作
    Step 4 − 将步骤3的输出存储回堆栈
    Step 5 − 扫描表达式,直到使用所有操作数
    Step 6 − 弹出堆栈并执行操作
    
    
    在C中实现-
    前缀表示法更易于人类阅读和理解,而对于诸如计算机这样的电子机器,后缀是可解析的最佳表达形式。我们将在这里看到一个程序,用于将中缀符号转换并评估为后缀符号-
    
    #include <stdio.h>
    #include <string.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+*
    Result is: 5