将中缀转换为前缀表达式
要通过计算机求解表达式，我们可以将其转换为后缀形式或前缀形式。在这里，我们将看到中缀表达式如何转换为前缀形式。
首先，中缀表达式反转。注意，对于反转，圆括号也将反转。
例如：表达式：A+B*(C-D)
反转后的表达式为：）D–C（*B+A
因此我们需要将左括号转换为右括号，反之亦然。
反转后，通过使用后缀中缀算法将表达式转换为后缀形式。之后，后缀表达式再次反转以获取前缀表达式。
输入输出
Input: Infix Expression: x^y/(5*z)+2 Output: Prefix Form Is: +/^xy*5z2
算法
infixToPrefix(infix)
输入-中缀表达式以转换为前缀形式。
输出- 前缀表达式。
Begin
reverse the infix expression
for each character ch of reversed infix expression, do
if ch = opening parenthesis, then
convert ch to closing parenthesis
else if ch = closing parenthesis, then
convert ch to opening parenthesis
done
postfix := find transformed infix expression to postfix expression
prefix := reverse recently calculated postfix form
return prefix
End示例
#include<iostream>
#include<stack>
#include<locale> //for function isalnum()#include<algorithm>
using namespace std;
int preced(char ch) {
if(ch == '+' || ch == '-') {
return 1; //Precedence of + or - is 1
}else if(ch == '*' || ch == '/') {
return 2; //Precedence of * or / is 2
}else if(ch == '^') {
return 3; //Precedence of ^ is 3
}else {
return 0;
}
}
string inToPost(string infix) {
stack<char> stk;
stk.push('#'); //add some extra character to avoid underflow
string postfix = ""; //initially the postfix string is empty
string::iterator it;
for(it = infix.begin(); it!=infix.end(); it++) {
if(isalnum(char(*it)))
postfix += *it; //add to postfix when character is letter or number
else if(*it == '(')
stk.push('(');
else if(*it == '^')
stk.push('^');
else if(*it == ')') {
while(stk.top() != '#' && stk.top() != '(') {
postfix += stk.top(); //store and pop until ( has found
stk.pop();
}
stk.pop(); //remove the '(' from stack
}else {
if(preced(*it) > preced(stk.top()))
stk.push(*it); //push if precedence is high
else {
while(stk.top() != '#' && preced(*it) <= preced(stk.top())) {
postfix += stk.top(); //store and pop until higher precedence is found
stk.pop();
}
stk.push(*it);
}
}
}
while(stk.top() != '#') {
postfix += stk.top(); //store and pop until stack is not empty
stk.pop();
}
return postfix;
}
string inToPre(string infix) {
string prefix;
reverse(infix.begin(), infix.end()); //reverse the infix expression
string::iterator it;
for(it = infix.begin(); it != infix.end(); it++) { //reverse the parenthesis after reverse
if(*it == '(')
*it = ')';
else if(*it == ')')
*it = '(';
}
prefix = inToPost(infix); //convert new reversed infix to postfix form.
reverse(prefix.begin(), prefix.end()); //again reverse the result to get final prefix form
return prefix;
}
int main() {
string infix = "x^y/(5*z)+2";
cout << "Prefix Form Is: " << inToPre(infix) << endl;
}输出结果
Prefix Form Is: +/^xy*5z2