前缀表达式--转换+求值

到现在写的比较多的是后缀表达式，然而到前缀表达式还没什么思路
这里整理一下中缀表达式转前缀表达式及前缀表达式的求值

中缀转前缀转换原则

有个比较简单的看法：（选择题可以用）
将中缀表达式按计算顺序加括号，前缀表达式则将括号中的运算符移到括号前面，后缀则移到后面，再将所有括号去掉即可
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中
若是操作符，如果符号栈为空，直接放入符号栈中；如果符号栈非空，则判断当前栈顶元素
1. 若栈顶为“）”，直接将操作符压入符号栈（从右往左扫描，先遇到的是右括号）
2. 若当前栈顶元素优先级>操作符优先级，栈顶元素移除，再比较移除后栈的栈顶元素优先级。直到栈顶元素优先级≤操作符，将操作符放入符号栈（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
using namespace std;
int main()
{
    string s;
    getline(cin,s);
    stack mark;
    map lst;
    lst['+'] = lst['-'] = 1;
    lst['*'] = lst['/'] = 2;
    bool flag=1;
    for(int i=0;ilst[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
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("%.1fn",exp());
    return 0;
}

因为是前缀表达式，操作符肯定都在前面，因此把操作符——入栈
若遇到数字，就取出一个操作符，两个操作数进行处理了然后继续循环，直到所有操作数处理完毕

完整思路：

用数组s接受前缀表达式，连同空格一起
将s全部压入堆栈A中
每次从堆栈A中取出一个字符x
1. 若是数字，看下一个字符y是数字还是空格
  - 若是空格，直接将x压入栈B
  - 若是小数点，再取小数点下一个数，直到遇到空格，合并得到完整小数，压入B
  - 若是数字，表示则表明x和y同为某一小数的小数部分，且y是x的前一位，则不断循环，直到找到小数点，再加上小数点后面的数字，3者合并，得到一个完整的小数，然后压入堆栈B中
2. 若是空格，忽略
3. 若是x运算符，则m=B.POP(),n=B.POP()，然后m，x，n运算，结果压入B中

总体来说，前缀表达式不用管优先级，遇到运算符就用

代码赶路ing……

前缀表达式--转换+求值

Python相关栏目本月热门文章