Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include "string"
- #include "conio.h"
- #include <cstdlib>
- #include <algorithm>
- #include <bits/stdc++.h>
- #include <stdio.h>
- #include <stdlib.h>
- using namespace std;
- template <class T>
- struct Node {
- T data;
- Node *next;
- Node(){
- next=NULL;
- }
- Node(T x){
- data=x;
- next=NULL;
- }
- };
- template <class T>
- class Stack{
- Node<T> *top=NULL;
- public:
- bool IsEmpty(){
- if(top==NULL)
- return true;
- else
- return false;
- }
- void Push(T x){
- Node<T> *n=NULL;
- n=new Node<T>(x);
- //n->data=x;
- if(IsEmpty())
- top=n;
- else{
- n->next=top;
- top=n;
- }
- }
- T Pop(){
- if(IsEmpty()==false){
- Node<T> *t=top;
- T x=top->data;
- top=top->next;
- t->next=NULL;
- delete t;
- return x;
- }
- }
- void display(){
- if(IsEmpty()==false){
- Node<T> *t=top;
- while(t->next!=NULL){
- cout<<t->data<<endl;
- t=t->next;
- }
- }
- }
- T Top(){
- if(!IsEmpty())
- return top->data;
- else
- exit(EXIT_FAILURE);
- }
- void Clear(){
- top=NULL;
- }
- };
- //Function to return precedence of operators
- int prec(char c)
- {
- if(c == '*' || c == '/')
- return 2;
- else if(c == '+' || c == '-')
- return 1;
- else
- return -1;
- }
- // The main function to convert infix expression
- //to postfix expression
- void infixToPostfix(string s)
- {
- Stack<char> st;
- st.Push('N');
- int l = s.length();
- string ns="";
- for(int i = 0; i < l; i++)
- {
- // If the scanned character is an operand, add it to output string.
- if((s[i] >= 'a' && s[i] <= 'z')||(s[i] >= 'A' && s[i] <= 'Z') || isdigit(s[i]))
- ns+=s[i];
- // If the scanned character is an ‘(‘, push it to the stack.
- else if(s[i] == '(')
- st.Push('(');
- // If the scanned character is an ‘)’, pop and to output string from the stack
- // until an ‘(‘ is encountered.
- else if(s[i] == ')')
- {
- while(st.Top() != 'N' && st.Top() != '(')
- {
- char c = st.Top();
- st.Pop();
- ns += c;
- }
- if(st.Top() == '(')
- {
- //char c = st.Top();
- st.Pop();
- }
- }
- //If an operator is scanned
- else{
- while(st.Top() != 'N' && prec(s[i]) <= prec(st.Top()))
- {
- char c = st.Top();
- st.Pop();
- ns += c;
- }
- st.Push(s[i]);
- }
- }
- //Pop all the remaining elements from the stack
- while(st.Top() != 'N')
- {
- char c = st.Top();
- st.Pop();
- ns += c;
- }
- cout << ns << endl;
- }
- //Driver program to test above functions
- int main()
- {
- string exp = "(6+9)/3";
- infixToPostfix(exp);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement