#include <iostream>
#include <string>
#include <stack>
using namespace std;
//i love macros
#define isOp(x) (x=='-'||x=='+'||x=='/'||x=='*')
#define isHigh(x) (x=='*'||x=='/')
#define isLow(x) (x=='-'||x=='+')
#define isSame(x, y) ((isHigh(x) && isHigh(y)) ||(isLow(x) && isLow(y)))
#define isClose(x) ((x==']')||(x==')')||(x=='}'))
#define isOpen(x) ((x=='[')||(x=='(')||(x=='{'))
string reverse(string s)
{
string tar;
for(int i = s.size(); i >= 0; i--)
{
tar += s[i];
}
return tar;
}
string infix2prefix(string source)
{
stack<char> output;
stack<char> ops;
string eq(reverse(source)); //reverse equation
char c;
//for each element in equation
for(int i = 0; i < eq.size(); i++)
{
c = eq[i]; //prevent repeated dereferencing
//if not /-+*[]{}()
if((!isOp(c))&&(!isClose(c))&&(!isOpen(c)))
output.push(c);
//if is )}]
if(isClose(c))
ops.push(c);
//if is /+-*^
if(isOp(c))
{
//if stack is empty put operator on stack
if(ops.empty())
{
ops.push(c);
}else{
//else if top of stack is )]or} push operator on stack
if(isClose(ops.top()))
{
ops.push(c);
}
//is precedence is the same or higher push it onto
//operator stack...else, push it straight to output
//stack
if(isSame(c, ops.top())||isHigh(c))
{
ops.push(c);
}else{
output.push(c);
}
}
}
//if ([or{
if(isOpen(c))
{
//move operator stack to output stack
while(!ops.empty())
{
output.push(ops.top());
ops.pop();
}
}
}
//put remaining operators on output stack
while(!ops.empty())
{
output.push(ops.top());
ops.pop();
}
//turn output stack into a string
eq = "";
while(!output.empty())
{
eq += output.top();
output.pop();
}
return eq;
}
int main()
{
string eq;
char c;
cin >> eq;
while(eq != "exit")
{
cout << infix2prefix(eq) << endl;
cin >> eq;
}
return 0;
}
لطفا" در صورت اشکال برام مشکل رو بفرستید.من دارم میام ایران.ممکنه که ی خورده دیرتر جواب بدم.
پاسخ با نقل قول