面试题77：前缀、中缀、后缀表达式的相互转换

本文主要是介绍面试题77：前缀、中缀、后缀表达式的相互转换，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：写个函数，一个根据中缀表达式写出后缀缀表达式

#include<iostream>  
#include <vector>
#include <stack>
using namespace std;bool IsOperator(char c)
{const char ops[] = "+-*/";for (int i = 0; i < sizeof(ops); i++){if (c == ops[i]) return true;}return false;
}/*
判断优先级：
如果a比b高，返回1,；如果相等，返回0；如果a比b低，返回-1.
*/
int Firster(char a, char b)
{if (a == '(') return -1;   //优先级最低if (a == '+' || a=='-'){if (b == '*' || b == '/') return -1;else return 0;}if (a == '*' || a == '/'){if (b == '+' || b == '-') return 1;else return 0;}return 0;  //这句只是为了消除警告
}/*
将前缀转为后缀
*/
void InfixToSuffix(const vector<char> infix, vector<char> &suffix)
{stack<char> oChar;int size = infix.size();char temp;//int index = 0;for (int i = 0; i < size; i++){temp = infix[i];if (temp == '(') oChar.push(temp);else if (temp == ')'){while (oChar.top() != '('){suffix.push_back(oChar.top());oChar.pop();}oChar.pop();}else{if (!IsOperator(temp)) oChar.push(temp);else{while (!oChar.empty() && Firster(oChar.top(), temp) >= 0) //理解这部分{suffix.push_back(oChar.top());oChar.pop();}oChar.push(temp);}}}while (!oChar.empty()){suffix.push_back(oChar.top());oChar.pop();}suffix.push_back('\0');
}int main(){char arr[] = "9+(3-1)*3+9/2";vector<char> infix(arr, arr + strlen(arr));vector<char> re;InfixToSuffix(infix, re);for (unsigned int i = 0; i < re.size(); i++)cout << re[i];cout << endl;return 0;
}

这篇关于面试题77：前缀、中缀、后缀表达式的相互转换的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---