Data structure Topic Note -03- Infix expression into postfix expression C language

Postfix expression, also known as inverse Pollan

Operators are placed after two operands, without parentheses, and are evaluated strictly from left to right in the order in which the operators appear (regardless of operator precedence rules).

For example, the suffix expression is “2 3 + 4 x 5 -“.

1) Scan from left to right, pressing a number onto the stack. (Here we push 2 and 3 onto the stack).

2) When the operation symbol ‘+’ is encountered, push out the first two elements on the top of the stack and calculate the value of 3 + 2 as 5. Push 5 onto the stack again.

3) Hit the number 4 and press onto the stack.

4) When ‘x’ is encountered, push the element from the top of the stack off the stack and evaluate. Calculate 4 x 5 = 20. Push 20 onto the stack.

5) Hit the number 5 and press onto the stack.

6) Finally ‘-‘, press out the two elements of the battle 5 20. Do the calculation 20-5 and get 15.

Infix expression (or infix notation)

Is a generic representation of an arithmetic or logical formula with operators in infix formThe operandThe infix expression is a common arithmetic representation.

So how do you convert an infix expression to a postfix expression?

1) Create a stack

2) Get infix expressions from left to right

2.1) Output a number directly

2.2) operators

A: The open parenthesis ‘(‘ is pushed directly

B: When a close parenthesis ‘(‘ is encountered, all elements before the open parenthesis are pushed off the stack. (PS: The open bracket also presses the stack, but we don’t print it out.)

C: Hits a multiplier ‘x’ or a divisor ‘/’ and pushes it onto the stack until it hits a lower-priority operator and pushes it off the stack.

D: A plus ‘+’ or a minus ‘-‘ is encountered. If the stack is empty, so directly onto the stack, otherwise, you need to stack priority operation in turn out stack symbols (here it is important to note that if the stack in addition to the operator priority than it is of the same priority operator, will in turn out stack) until the stack is empty or encounter left parenthesis.

E: Finally, when the retrieval is complete, the remaining operation symbols are pushed off the stack in turn.

For example, to convert an infix expression “1+((2+3)x4)-5” to a suffix expression:

So, the final suffix expression is: ‘1 2 3 + 4 x + 5 -‘.

Code implementation:

First, define a stack.

typedef char ElementType;
typedef struct SNode *Stack;
#define INITSIZE 20#define LEN sizeof (ElementType) struct SNode{ ElementType *base; Point to bottom ElementType *top; int StackSize; };Copy the code

Create a stack

void CreateStack(Stack S){
    S->base=(ElementType *)malloc(LEN*INITSIZE);// Point S's base directly to an array of charactersassert(S->base! =NULL); S->top=S->base; S->StackSize=INITSIZE; }Copy the code

Onto the stack

void Push(Stack S,ElementType X){
    if(S->top - S->base>=S->StackSize){
        S->base=(ElementType*) realloc(S->base,sizeof (ElementType)*(S->StackSize+10));// If you don't have enough spaceassert(S->base! =NULL); S->top=S->base+S->StackSize; S->StackSize+=10;
    }
    *S->top=X;
    S->top++;
}
Copy the code

Return stack length

int StackLength(Stack S){
    return (S->top - S->base);
}
Copy the code

Press the stack

int Pop(Stack S,ElementType *X){// An address is passed in
    if(! StackLength(S)){ printf("Stack empty \n");
        return 0;
    }
    S->top--;
    *X=*S->top;
    return 1;
}
Copy the code

An infix expression is converted to a postfix expression

void Change(Stack S,ElementType str[]){// The core function
    int i=0;
    ElementType X;
    CreateStack(S);
    while(str[i]! =' ') {while (isdigit(str[i])){
            printf("%c",str[i++]);
            if(! isdigit(str[i])){ printf(""); }}if(str[i]=='+' || str[i]==The '-') {if(! StackLength(S)){ Push(S,str[i]); }else{
                do{
                    Pop(S,&X);
                    if(X=='('){
                        Push(S,X);
                    } else{
                        printf("%c ",X); }}while(StackLength(S) && X! ='('); Push(S,str[i]); }}else if(str[i]==') '){
            Pop(S,&X);
            while(X! ='('){
                printf("%c ",X); Pop(S,&X); }}else if(str[i]==The '*' || str[i]=='/' || str[i]=='('){
            Push(S,str[i]);
        } else if(str[i]=='\ 0') {break;
        } else{
            printf("Input error \n");
            return;
        }
        i++;
    }
    while (StackLength(S)){
        Pop(S,&X);
        printf("%c ",X); }}Copy the code

Testing:

int main(void){

    ElementType str[30];
    Stack S=(Stack) malloc(sizeof (struct SNode));
    gets(str);
    Change(S,str);
    return 0;
}
Copy the code

Note: Stack S=(Stack) malloc(sizeof (struct SNode)); You have to write it this way instead of Stack S; Because when we’re defining the Stack we’re rewriting the alias typedef struct SNode *Stack; The structure pointer Stack is defined.

The difference between struct pointer variables and struct variables is mentioned here. A structure variable defines a structure directly, while a structure pointer variable defines a pointer, and it must be associated with a structure to be used as a structure, either by using malloc to apply for space or assigning an address to another object that points to the structure.