Scribd Logo
Upload

Welcome to Scribd!

  • 8 views

    Ds Assignment 4

    Uploaded by

    RAGHVANI ISHA
    This document provides code to convert expressions between infix, prefix, and postfix notations using stacks. It includes functions to push and pop from a stack, check precedence of operators, and convert between the different notations. The code samples show how to set up the stacks, evaluate precedence, and manipulate the expressions as they are traversed to convert between infix, prefix, and postfix.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd

    Ds Assignment 4

    Uploaded by

    RAGHVANI ISHA
    8 views6 pages
    This document provides code to convert expressions between infix, prefix, and postfix notations using stacks. It includes functions to push and pop from a stack, check precedence of operators, and convert between the different notations. The code samples show how to set up the stacks, evaluate precedence, and manipulate the expressions as they are traversed to convert between infix, prefix, and postfix.

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document provides code to convert expressions between infix, prefix, and postfix notations using stacks. It includes functions to push and pop from a stack, check precedence of operators, and convert between the different notations. The code samples show how to set up the stacks, evaluate precedence, and manipulate the expressions as they are traversed to convert between infix, prefix, and postfix.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    8 views6 pages

    Ds Assignment 4

    Uploaded by

    RAGHVANI ISHA
    This document provides code to convert expressions between infix, prefix, and postfix notations using stacks. It includes functions to push and pop from a stack, check precedence of operators, and convert between the different notations. The code samples show how to set up the stacks, evaluate precedence, and manipulate the expressions as they are traversed to convert between infix, prefix, and postfix.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    You are on page 1of 6

    DS ASSIGNMENT 4

    ISHA RAGHVANI CS-B 33

    4. WAP to convert Infix expression into equivalent Postfix and Prefix format
    using Stack.

    1. Infix to Prefix

    # include <stdio.h>
    # include <string.h>
    # define MAX 20

    void infixtoprefix(char infix[20],char prefix[20]);

    int top=-1
    char stack[MAX];

    char pop() {
    char a;
    a=stack[top];
    top--;
    return a;
    }

    void push(char symbol) {


    top++;
    stack[top]=symbol;
    }

    int precedence(char symbol) // returns the value that helps in the precedence
    {
    switch(symbol) {
    case '+':
    case '-':
    return 2;
    break;
    case '*':
    case '/':
    return 4;
    break;
    case '$':
    case '^':
    return 6;
    break;
    case '#':
    case '(':
    case ')':
    return 1;
    break;
    }
    }

    int isOperator(char symbol) {


    switch(symbol) {
    case '+':
    case '-':
    case '*':
    case '/':
    case '^':
    case '$':
    case '&':
    case '(':
    case ')':
    return 1;
    break;
    default:
    return 0;
    // returns 0 if the symbol is other than given above
    }
    }

    void infixtoprefix(char infix[20],char prefix[20]) {


    int i,j=0;
    char symbol;
    stack[++top]='#';
    strrev(infix);
    for (i=0;i<strlen(infix);i++) {

    symbol=infix[i];

    if (isOperator(symbol)==0) {
    prefix[j]=symbol;
    j++;
    }
    else {
    if (symbol==')') {
    push(symbol);
    }
    else if(symbol == '(') {
    while (stack[top]!=')') {
    prefix[j]=pop();
    j++;
    }
    pop();
    }
    else {
    if (precedence(stack[top])<=precedence(symbol)) {
    push(symbol);
    }
    else {
    while(precedence(stack[top])>=precedence(symbol)) {
    prefix[j]=pop();
    j++;
    }
    push(symbol);
    }

    }
    }

    while (stack[top]!='#') {
    prefix[j]=pop();
    j++;
    }
    prefix[j]='\0';
    }
    int main() {
    char infix[20],prefix[20],postfix[20],temp;
    printf("\nEnter infix operation: ");
    gets(infix);
    printf("\nInfix to Prefix Conversion: ");
    infixtoprefix(infix,prefix);
    strrev(prefix);
    puts((prefix));

    Output:
    2. Infix to Postfix
    3. # include <stdio.h>
    4. # include <string.h>
    5. #include <stdlib.h>
    6. #define MAX 100
    7.
    8. char stack[MAX];
    9. char infix[MAX],postfix[MAX];
    10.int top=-1;
    11.
    12.void push(char);
    13.char pop();
    14.int isEmpty();
    15.void inToPost();
    16.int space(char);
    17.void print();
    18.int precedence(char);
    19.
    20.int main(){
    21. printf("\nEnter infix operation: ");
    22. gets(infix);
    23. inToPost();
    24. print();
    25. return 0;
    26.}
    27.

    28.int precedence(char symbol){


    29. switch (symbol)
    30. {
    31. case '^' :
    32. return 3;
    33. case '/':
    34. case '*' :
    35. return 2;
    36. case '+':
    37. case '-' :
    38. return 1;
    39.
    40. default:
    41. return 0;
    42. }
    43.
    44.}
    45.void inToPost()
    46.{
    47.
    48. int i,j=0;
    49. char symbol,next;
    50. for(int i=0;i<strlen(infix);i++)
    51. {
    52.
    53.
    54. symbol=infix[i];
    55. if(!space(symbol))
    56. {
    57. switch(symbol)
    58. {
    59. case '(':
    60. push(symbol);
    61. break;
    62. case ')':
    63. while((next=pop())!='('){
    64. postfix[j++]=next;
    65. break;
    66. }
    67. case '+':
    68. case '-':
    69. case '*':
    70. case '/':
    71. case '^':
    72. while(!isEmpty() && precedence(stack[top]) >= precedence(symbol))
    73. postfix[j++]=pop();
    74. push(symbol);
    75. break;
    76. default:
    77. postfix[j++]=symbol;
    78. }
    79. }
    80.
    81.
    82. }
    83.
    84. while(!isEmpty())
    85.
    86. postfix[j++]=pop();
    87. postfix[j]='\0';
    88.
    89.
    90.}
    91.
    92.int space(char c){
    93. if(c== ' ' || c=='\t')
    94. return 1;
    95. else
    96. return 0;
    97.}
    98.void print(){
    99. int i=0;
    100. printf(" PostFix expression is: ");
    101. while(postfix[i]){
    102. printf("%c",postfix[i++]);
    103. }
    104. printf("\n");
    105. }
    106. void push( char c)
    107. {
    108. if(top == MAX-1){
    109. printf("Stack is full");
    110. return;
    111. }
    112. top++;
    113. stack[top]=c;
    114. }
    115. char pop(){
    116. char c;
    117. if(top==-1){
    118. printf("Stack is empty");
    119. exit(1);
    120. }
    121. c = stack[top];
    122. top = top - 1;
    123. return c;
    124. }
    125. int isEmpty(){
    126. if(top == -1)
    127. return 1;
    128. else
    129. return 0;
    130. }
    131.

    OUTPUT:

    You might also like