逆波兰表达式的生成与计算

普通表达式一般由数字、变量与+-*/()运算符号组成。

例如:

(a+b)*3 - (a-b)/2

其逆波兰表达式是: a b + 3 * a b - 2 / -

本质上,普通表达式是中序表达式,逆波兰表达式是后序表达式。

一)、由普通表达式生成逆波兰表达式

  1、初始化1个逆波兰字符串变量outstr,以及1个符号栈;自左向右输入表达式串;  2、如果当前字符为数值或变量,则直接添加到逆波兰字符串后 outstr;

  3、如果当前字符为运算符号,如果是“(”,则直接压入符号栈;如果是“)”,则从栈中逐项pop运算符号,追加在outstr后;如果是其他运算符号,比较当前与栈顶的运算符优先级,如果当前低,则pop栈顶运算符,压入当前运算符号;如果当前的高,则直接压入栈中;

  4、遇到结束符号时,逐项从栈中pop运算符项;

二)、计算逆波兰表达式的值

   1、自左向右输入逆波兰表达式串;

   2、如果当前为操作数,则直接压入栈;

   3、如果当前为运算符号,则从栈顶两个进行计算,并将计算结果压入栈中;

   4、最后从栈中pop出最终运算结果。

原文地址:https://www.cnblogs.com/feika/p/3607431.html