#include "InversePolandexpression.h"
InversePolandexpression::InversePolandexpression()
{
}
InversePolandexpression::~InversePolandexpression()
{
}
bool InversePolandexpression::isHigherPriority(int left, int right)
{
if (left > right)
{
return true;
}
else
{
return false;
}
}
int InversePolandexpression::getPrecedence(char now)
{
switch (now)
{
case '+':
case '-':
return 1;
case '@':
case '*':
case '/':
return 2;
case '^':
case '%':
return 3;
case'#':
default:
return 0;
}
}
string InversePolandexpression::translateStringToExpression(string infix)
{
string result;
m_stack.push('#');//为主栈自动添加一个标记符
for (int i = 0; i < infix.length(); i++)
{
if (infix[i] == '#')
{
break;
}
if (isalpha(infix[i]) || isdigit(infix[i]))//如果当前字符为字母或数字
{
result += infix[i];
}
else if (infix[i] == '(')//如遇左括号,则无条件入栈,且起到间隔作用
{
m_stack.push(infix[i]);
}
else if (infix[i] == ')')//如遇右括号,则开始匹配左括号,并将它们都去掉,一次只是去掉一对括号
{
if (!deleteLeftAndRightBracket(m_stack))//如果没有与之匹配的左括号
{
return "error";//返回异常
}
}
else
{
int now_presedence = getPrecedence(infix[i]);//当前字符的优先级
int top_of_stack_presedence = getPrecedence(m_stack.top());//栈顶字符的优先级
if (isHigherPriority(now_presedence, top_of_stack_presedence))//若当前字符的优先级高于栈顶字符的优先级
{
m_stack.push(infix[i]);//入栈
}
else
{
while (!isHigherPriority(now_presedence, top_of_stack_presedence) && m_stack.top() != '#'&& m_stack.top() != '(')//当优先级一直处于低于或等于状态
{
result += m_stack.top();//栈顶元素添加到结果中
m_stack.pop();
}
m_stack.push(infix[i]);//入栈
}
}
}
while (!m_stack.empty() && m_stack.top() != '#')
{
result += m_stack.top();//栈顶元素添加到结果中
m_stack.pop();
}
return result;
}
bool InversePolandexpression::deleteLeftAndRightBracket(stack<char>& m_s)
{
stack<char> temp;
while (!m_s.empty() && m_s.top() != '(')//如果栈顶不是右括号且栈非空
{
temp.push(m_s.top());
m_s.pop();
}
if (m_s.empty())//证明没有与右括号匹配的左括号
{
return false;
}
else if (m_s.top() == '(')//如果匹配上了左括号
{
m_s.pop();//弹出左括号
while (!temp.empty())//把(之上的元素压入栈
{
m_s.push(temp.top());
temp.pop();
}
return true;
}
}