code. compile. run. debug. share.
Source Code
Language
#include <iostream>
#include <cmath>
#include <stack>
using namespace std;
string Infix2Prefix(string infix)
{
string postfix = "";
infix = "(" + infix + ")";
int len = infix.length();
int i = 0;
stack<char>operato;
//reverse
string reverse="";
for (int i = len - 1; i >= 0; --i)
{
if (infix[i] == '(') reverse += ')';
else if (infix[i] == ')') reverse += '(';
else reverse += infix[i];
}
infix = reverse;
while(i < len)
{
char c = infix[i];
if(isdigit(c))
{
string operand = "";
while(isdigit(c))
{
operand += c;
c = infix[++i];
}
postfix += operand;
postfix += ' ';
--i;
}
else if(infix[i] == '(')
operato.push(infix[i]);
else if(infix[i] == ')')
{
while(!operato.empty() && operato.top() != '(')
{
postfix += operato.top();
postfix += ' ';
operato.pop();
}
operato.pop();
}
else if((infix[i]=='+')||(infix[i]=='-')||(infix[i]=='*')||(infix[i]=='/')||(infix[i]=='^'))
{
if((infix[i]==operato.top()))
{
// postfix += operato.top();
// postfix += ' ';
// operato.pop();
operato.push(infix[i]);
}
else if(((operato.top()=='*') || (operato.top()=='/') || (operato.top()=='^')) && ((infix[i]=='+')||(infix[i]=='-')))
{
postfix += operato.top();
postfix += ' ';
operato.pop();
operato.push(infix[i]);
}
else if((operato.top()=='^') && ((infix[i]=='*') || (infix[i]=='/') || (infix[i]=='+')||(infix[i]=='-')))
{
postfix += operato.top();
postfix += ' ';
operato.pop();
operato.push(infix[i]);
}
else if(((operato.top()=='*') && (infix[i]=='/')) || ((operato.top()=='/') && (infix[i]=='*')))
{
// postfix += operato.top();
// postfix += ' ';
// operato.pop();
operato.push(infix[i]);
}
else if(((operato.top()=='-') && (infix[i]=='+')) || ((operato.top()=='+') && (infix[i]=='-')))
{
// postfix += operato.top();
// postfix += ' ';
// operato.pop();
operato.push(infix[i]);
}
else operato.push(infix[i]);
if((operato.top() == '(')||operato.empty())
operato.push(infix[i]);
else
{
char operator_1 = operato.top();
operato.pop();
char operator_2 = operato.top();
operato.pop();
if(operator_1 == operator_2)
{
operato.push(operator_2);
operato.push(operator_1);
}
else if(((operator_2=='*') || (operator_2=='/') || (operator_2=='^')) && ((operator_1=='+')||(operator_1=='-')))
{
postfix += operator_2;
postfix += ' ';
operato.push(operator_1);
}
else if(((operator_2=='-') && (operator_1=='+')) || ((operator_2=='+') && (operator_1=='-')))
{
operato.push(operator_2);
operato.push(operator_1);
}
else if(((operator_2=='*') && (operator_1=='/')) || ((operator_2=='/') && (operator_1=='*')))
{
operato.push(operator_2);
operato.push(operator_1);
}
else
{
operato.push(operator_2);
operato.push(operator_1);
}
}
}
++i;
}
while(!operato.empty())
{
if((operato.top() == '(') || (operato.top() == ')'))
operato.pop();
else
{
postfix+= operato.top();
postfix += ' ';
operato.pop();
}
}
//prefix
string prefix;
for (int i = postfix.length() - 2; i >= 0; --i)
{
prefix += postfix[i];
}
cout << infix << endl;
cout << postfix << endl;
return prefix;
}
int main()
{
string infix = "59+107*83*72*91/(27-(112*153)*(111+76))";
// cin >> infix;
cout << Infix2Prefix(infix) << " ";
return 0;
}
Compiling Program...
Standard Input:
Interactive Console
Text
Program is not being debugged. Click "Debug" button to start program in debug mode.
| # | Function | File:Line |
|---|
| Variable | Value |
|---|
| Register | Value |
|---|
| Expression | Value |
|---|
| # | Description |
|---|