Topic:

Design an algorithm that converts a general arithmetic expression into an inverse Polish expression and evaluates the inverse Polish expression.

Analysis:

(1) general arithmetic expression (infix expression), such as #3*(4+2)/2-5#, # is the expression delimit, the inverse Polish expression (suffix expression), such as the expression of the suffix expression is: 3 4 2 + * 2/5 -.

(2) Suppose the infix expression has five operators: +, -, *, / and #, and the priority of the operators is (), *, /, +, – and # from high to low. If there are parentheses, calculate the parentheses first, and then calculate the parentheses outside. Multilayer parentheses are carried out from inside to outside.

(3) Converting infix expressions into postfix expressions requires a temporary stack OPTR temporary operator.

Pseudocode implementation

1, infix expression into postfix expression

1. Initialize stack OPtr to#;2. Scanning each character of an expression from left to right, perform the following operations 2.1 If the current character is an operation object, print that character and process the next character; 2.2 If the current character is an operator and has a higher priority than the top of the stack opTR operator, the character will be pushed to the opTR and the next character will be processed. 2.3 If the current character is an operator and the priority level is lower than that of the top stack opTR operator, the top stack element of the stack OPTR will be ejected and output, the current character will be pushed into the stack OPTR, and the next character will be processed; 2.4 If the current character is an operator and the priority is equal to that of the top stack operator of stack OPTR, the top stack element of stack OPTR is popped, the current character is pushed into the stack opTR, and the next character is processed.Copy the code

Second, expression calculation

1. Initialization stack OPnd is empty; 2. Scanning each character of a postfix expression (inverse Polish expression) from left to right, do the following; 2.1 If the current is an operation object, opND will be pushed to process the next character; 2.2 If the current character is an operator, the two operands are removed from the stack OPnd, the operation is performed and the result is pushed into the stack OPnd, and the next character is processed; 3. Output the top element of stack OPnd, that is, the operation result of expression.Copy the code

Code implementation

1, infix expression into postfix expression

Void NifixPost(char *nifix, char *postfix){int I = 0, j = 0; Sqstack *optr; optr = InitStack(); Push(optr,The '#');
  while(nifix[i] ! =The '#') {
    if(nifix[i] == '(')
    {
      Push(optr, '(');
    }

    else if (nifix[i] == ') ')
    {
      while(GetTop(optr) ! ='('){
        postfix[j++] = Pop(optr);
      }
      Pop(optr);
    }

    else if ((nifix[i] >= '0' && nifix[i] <='9') || nifix[i] == '. ') {while ((nifix[i] >= '0' && nifix[i] <='9') || nifix[i] == '. ') {
        postfix[j++] = nifix[i++];
      }
      postfix[j++] = ' ';
      i--;
    }

    else {
      char s1, optrtop;
      s1 = nifix[i];
      optrtop = GetTop(optr);
      if (CtoRank(s1) <= CtoRank(optrtop)) {
        postfix[j++] = Pop(optr);
        i--;
      }
      else {
        Push(optr, s1);
      }

    }
    i++;
  }
    while(IsEmpty(optr) ! = -1){ postfix[j++] = Pop(optr); } postfix[j] ='\ 0';

  printf("\n");
}
Copy the code

Second, expression calculation

Double Myatof(char * STR){double m=0,n=0,x=1; int flag=1;while(*str! ='\ 0')
	{
		if(*str<'0'|| *str >'9' )
		{	
			if(*str =='. '// check the decimal point before and after {flag=0; str++;continue;
			}
			return 0;
		}
		if(flag==1) // The integer before the decimal point {m*=10; m+=*str-'0';
		}
		else{x*=0.1; n+=x*(*str-'0');
		}
		str++;
	}
	returnm+n; } // Double ComputeTwoNum (double a,double b,char c) {double temp; switch(c) {case '+':
    temp = a + b;
    break;
    case The '-':
    temp = a-b;
    break;
    case The '*':
    temp = a * b;
    break;
    case '/':
    temp = a / b;
    break;
    case A '^':
      {
        int i = 0;
        temp = 1;
        while(fabs(i-b) > 1e-6) { temp *= a; i++; }}}returntemp; } // Double ComputeExpresion (char *postfix) {int I = 0,j; char currentExp[STACK_SIZE];printf("\n");

  while(postfix[i] ! =The '#') 
  {
    if(postfix[i] >= '0' && postfix[i] <= '9' || postfix[i] == '. ')
    {
      j = 0;
      while (postfix[i] >= '0' && postfix[i] <= '9' || postfix[i] == '. ')
      {
        currentExp[j++] = postfix[i++];
      }
      currentExp[j] = '\ 0';
      OPTD[++TopTd] = Myatof(currentExp);

    } else if (postfix[i] == ' ') {
      i++;
    } 
    else// The current character is the operator {double a, b; // b = Pop(optd); // a = Pop(optd); b = OPTD[TopTd--]; A = OPTD[TopTd]; a = OPTD[TopTd]; OPTD[TopTd] = ComputeTwoNum(a, b, postfix[i]); i++; }}return OPTD[TopTd]; 
}
Copy the code