到现在写的比较多的是后缀表达式，然而到前缀表达式还没什么思路
这里整理一下中缀表达式转前缀表达式及前缀表达式的求值
中缀转前缀
转换原则
有个比较简单的看法：（选择题可以用）
将中缀表达式按计算顺序加括号，前缀表达式则将括号中的运算符移到括号前面，后缀则移到后面，再将所有括号去掉即可
eg.
中缀表达式：a+b*c-(d+e)
所有运算单位加括号：((a+(b*c))-(d+e))
1. 前缀表达式：把运算符号移动到对应的括号前面
变为：-( +(a *(bc)) +(de))
把括号去掉：-+a*bc+de 前缀表达式出现
2. 后缀表达式：把运算符号移动到对应的括号后面
变为：((a(bc)* )+ (de)+ )-
把括号去掉：abc*+de+- 后缀表达式出现
注意要在运算符对应括号层级移动
实现思路
不同于后缀表达式，前缀表达式相当于倒着扫描（从右往左）；且后缀表达式可以直接输出，前缀要先放到栈里再弹出（实现翻转）（即前缀出来首先是反着的）
先看一下转前缀与转后缀的对比，下面再仔细写实现思路
从右往左扫描：
- 若是操作数，直接放到栈prefix中
- 若是操作符，如果符号栈为空，直接放入符号栈中；如果符号栈非空，则判断当前栈顶元素
- 若栈顶为“）”，直接将操作符压入符号栈（从右往左扫描，先遇到的是右括号）
- 若当前栈顶元素优先级>操作符优先级，栈顶元素移除，再比较移除后栈的栈顶元素优先级。直到栈顶元素优先级≤操作符，将操作符放入符号栈（NT：不同于后缀，这里是有等于，即等于时也先不输出——>优先级等先输出后面的）
- 若遇到右括号，直接入栈
- 若遇到左括号，将左右括号之间的符号全部移除到prefix中（左括号不入栈，注意最后将右括号弹出）
- 重复1-4，直到最后一个字符被读入
- 判断当前栈是否为空，若非空，将栈中元素依次移到prefix中
- 依次弹出prefix栈（实现翻转）
代码
先转一个后缀
python
from pythonds.basic.stack import Stack
def infixToPostfix(infixexpr):
prec = {}
prec["*"] = 3
prec["/"] = 3
prec["+"] = 2
prec["-"] = 2
prec["("] = 1
opStack = Stack()
postfixList = []
tokenList = infixexpr.split()
for token in tokenList:
if token in "QWERTYUIOPASDFGHJKLZXCVBNM" or token in "1234567890":
postfixList.append(token)
elif token == '(': # 左括号直接压入栈中
opStack.push(token)
elif token == ')': # 读到右括号就把栈中的操作符弹出直到读到(
topToken = opStack.pop()
while topToken != '(':
postfixList.append(topToken)
topToken = opStack.pop()
else:
while (not opStack.isEmpty()) and \
(prec[opStack.peek()] >= prec[token]): # 只要栈里面的操作符比目前读到的操作符优先级高，就优先输出栈中的操作符
postfixList.append(opStack.pop())
opStack.push(token) # 将读到的字符压入栈中
while not opStack.isEmpty(): # 将栈中的剩余字符全部弹出
postfixList.append(opStack.pop())
return " ".join(postfixList)
print(infixToPostfix(input()))
C++
#include<bits/stdc++.h>
using namespace std;
int main()
{
string s;
getline(cin,s);
stack<char> mark;
map<char,int> lst;
lst['+'] = lst['-'] = 1;
lst['*'] = lst['/'] = 2;
bool flag=1;
for(int i=0;i<s.length();i++)
{
//先处理直接输出的——数字
if(isdigit(s[i]) || s[i]=='.' || ((!i||s[i-1]=='(') && (s[i]=='+' || s[i]=='-')))
{
if(!flag) cout << " ";
else flag=0;
if(s[i]!='+') cout << s[i];
while(s[i+1]=='.' || isdigit(s[i+1]))
cout << s[++i];
}else{
if(s[i]=='(') mark.push(s[i]);
else if(s[i]==')')
{
while(!mark.empty()&&mark.top()!='(')
{
cout << " " << mark.top();
mark.pop();
}
mark.pop();
}
else if(mark.empty() || lst[s[i]]>lst[mark.top()]) mark.push(s[i]);
else{
while(!mark.empty()&&lst[mark.top()]>=lst[s[i]])
{
cout << " " << mark.top();
mark.pop();
}
mark.push(s[i]);
}
}
}
while(!mark.empty())
{
cout << " " << mark.top();
mark.pop();
}
}
前缀
正在调试中ing…
前缀表达式求值
💿 借题👉PTA
最简单的就像样例中一样，没有小数和负数，先完成这个
按刚刚实现的思路，求值也得是先求后面（倒着求）
先跑到最里面——>堆栈 or 递归
用递归实现起来更直观（毕竟底层用的堆栈）
#include<bits/stdc++.h>
using namespace std;
double exp()
{
char s[35];
cin >> s;
switch (s[0])
{
case '+':
return exp() + exp();
case '-':
return exp() - exp();
case '*':
return exp() * exp();
case '/':
return exp() / exp();
default:
return atof(s);
}
}
int main()
{
printf("%.1f\n",exp());
return 0;
}
因为是前缀表达式，操作符肯定都在前面，因此把操作符——入栈
若遇到数字，就取出一个操作符，两个操作数进行处理了然后继续循环，直到所有操作数处理完毕
完整思路：
- 用数组s接受前缀表达式，连同空格一起
- 将s全部压入堆栈A中
- 每次从堆栈A中取出一个字符x
- 若是数字，看下一个字符y是数字还是空格
- 若是空格，直接将x压入栈B
- 若是小数点，再取小数点下一个数，直到遇到空格，合并得到完整小数，压入B
- 若是数字，表示则表明x和y同为某一小数的小数部分，且y是x的前一位，则不断循环，直到找到小数点，再加上小数点后面的数字，3者合并，得到一个完整的小数，然后压入堆栈B中
- 若是空格，忽略
- 若是x运算符，则m=B.POP(),n=B.POP()，然后m，x，n运算，结果压入B中
- 若是数字，看下一个字符y是数字还是空格
总体来说，前缀表达式不用管优先级，遇到运算符就用
代码赶路ing……