上一节:
下一节:

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

  • 表达式解析

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

  • 中缀符号

    我们用中缀表示法编写表达式，例如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
上一节:
下一节: