数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法学将中缀表达式转换为前缀表达式
若要让计算机求解表达式，我们可以将其转换成后缀形式或前缀形式。这里我们将介绍中缀表达式如何转换为前缀形式。
首先反转中缀表达式。请注意反转时左右括号也要反转。
例如：表达式：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
更新日期： 2020 年 6 月 17 日
6000+ 次浏览
广告