Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Function: convertToPostfix
- Input parameter: infix as string
- Output return value: postfix as string
- 1. Create an empty string to hold string our function will build, this is the post fix string.
- 2. Set a unary flag to true.
- 3. Create an empty stack of string.
- 4. Create an object of type CStringTokenizer to tokenize the infix string with the delimiters "()^+-/%* ", and set flag for including delimiter to true.
- 5. while our CStringTokenizer object has more tokens:
- A. Create a token string holding the next token with any trailing whitespaces trimmed.
- B. if (token is equal to "") // do nothing
- C. else if:
- i. if (token is equal to "(":
- a. Push(token) onto the stack.
- ii. else if (token is equal ")":
- a. Create a string holding the operator character.
- b. while (!(operator = pop()) is equal to "("):
- 1. postfix string += " " + operator.
- iii. else if (token is equal to "*" or token is equal to "^" or
- token is equal to "+" or token is equal to "-" or token is equal to "%" or token is equal to "/"):
- a. if (unary==true):
- 1. token = "u" + token;
- // a unary op always goes on
- // the stack without popping any other op
- 2. Push(token) onto the stack
- iv. else:
- a. Create an integer variable holding the operatorPrecedence(token)
- b. While (!stack.isEmpty() and !stack.peek() is equal to "(")
- and operatorPrecedence(stack.peek()) >= p):
- 1. Create a string holding the operator with the return value of stack.pop();
- 2. postfix string += " " + op;
- c. Push(token) onto stack.
- v. unary = true; // if an operator is after this one, ithas to be unary
- D. else // Else for if statement in 5B
- postfix += " |" + token + "|";
- unary = false; // any operator after an operand is binary
- 6. While (!stack.isEmpty()) {
- A.Create a string holding the operator with the return value of stack.pop();
- B. post fix string += " " + op;
- 7. return postfix;
- Function: operatorPrecedence
- Input parameter: operator of type string
- Output return value: integer holding precedence level
- 1. if (operator is equal to "u-" or operator is equal to "u+"): return 3 //highest level operator
- 2. else if (operator is equal to "^"): return 2
- 3. else if (operator is equal to "*" or operator is equal to"/"
- or operator is equal to "%"): return 1
- 4. else if (operator is equal to "-" or operator is equal to "+"):
- return 0;
- 5. else {
- return 0;
- Main function test driver:
- 1. Prompt: "\nEnter an infix expression to convert: "
- 2. Read in a string input from keyboard (highly recommend using getline function).
- 3. Create string holding result of convertToPostfix(input).
- 4. Output the result to the terminal screen.
Advertisement
Add Comment
Please, Sign In to add comment