中缀表达式转后缀表达式java,前缀表达式java

　　00-1010 1.概念2。算法流程3代码实现

　　但是，这种表达方式不利于计算机计算。通过某种方式将前缀表达式转化为后缀表达式，便于计算机计算。比如3(5 *(2 ^ 3)7)的后缀表达式是3，5，2，3，*，7，这个表达式计算机很容易计算。为什么很容易计算？通过算法流程2，我们会有深刻的理解。

　　00-1010如何将中缀表达式转换成后缀表达式？比如把3 (5*(2 3) 7)转换成后缀表达式的过程呢？

　　操作员优先级：

　　、-小于*、/等于-*等于/左括号和右括号被视为特殊运算符。(如果遇到(不判断优先级直接进入操作符栈，会遇到)，不判断优先级直接退出操作符栈)

　　算法大致把握以下过程：

　　准备两个栈，一个是数字栈A，一个是运算符栈(，-，*，/(，))B等。

　　1.0对于数字栈A，直接进入数字栈A。

　　2.0对于运营商栈B，有几种情况。

　　2.1将(运算符直接命中堆栈。

　　2.2遇到“)”运算符时，继续将运算符栈B推出栈，直到遇到“)”。(将( to )之间的弹出操作符依次放入堆栈A)

　　2.3遇到，-，*/时，比较当前元素的优先级(假设当前元素为当前)和B栈的top运算符(假设top元素为top)。

　　2.3.1如果top=current，堆栈b将弹出堆栈并循环比较，直到top current退出循环并将current放入堆栈。

　　2.3.2如果top电流，直接将电流投入b堆。

　　3.0扫描整个字符串，如果B栈中有运算符，则依次堆栈到A中。

　　按照上面算法演示3的流程(5*(2 3) 7):

　　1，命中3，3，入栈A [3，]2，命中，入栈B [，]3，命中(，入栈B [，(]4，命中5，入栈A [3，5]5，命中*，优先级*大于(，入栈B [，(，*]6，命中。B:[，(，*] A:[3，5，2，3，]11，遭遇战优先级小于B的顶元素*，所以*从B推出栈，进入A，进入B. B: [，(，] A:[3，5，2，3，*] 12，hit 7，进入栈A [3，5，2，3，*，7] 13，hit，弹出栈B，直接到 (，和如果没有，弹出B栈的元素，输入A，目前不为空，所以A栈的最后一个元素是A: [3，5，2，3，*，7，]

　　所以A最后的后缀表达式是3，5，2，3，*，7，

　　计算机将如何计算这个？流程如下：

　　当数字直接命中运算符时，会直接弹出两个顶部元素。运算符计算后，结果将被推入堆栈。在步骤1和步骤2之后，堆栈中将只有一个元素，这是表达式的结果。

　　让我们来练习一下：

　　1，把数字3，5，2，3直接打到栈顶A[3，5，2，3]2，打并弹出栈顶2，3，加起来5进栈A[3，5，5]3，打*，弹出栈顶5，5，相乘得到25进栈A[3，25]4，

　　从上面可以知道，计算机很容易计算，从左到右扫描就可以得到结果。

　　00-1010mid2post后缀表达式

　　CalcPostExp获取后缀表达式求值。

　　CmpPriority优先级比较

　　//priority bool CMP priority(char top，char cur)//将当前字符的优先级与第一个字符的优先级进行比较，如果第一个字符的优先级高，则返回true { if((top== top==-)(cur==

　　cur == -))return true;if ((top == * top == /) && (cur == + cur == - top == * top == /))return true;if (cur == ))return true;return false;}求后缀表达式求值

vector<string> mid2post(string &str){vector<string>vstr;stack<char>cstack;for (int i = 0;i<str.size();++i)//扫描字符串{string temp = "";if (str[i] >= 0 && str[i] <= 9)//若是数字{temp += str[i];while (i + 1<str.size() && str[i + 1] >= 0 && str[i + 1] <= 9){temp += str[i + 1];//若是连续数字++i;}vstr.push_back(temp);}else if (cstack.empty() str[i] == ()//若栈空或者字符为(cstack.push(str[i]);else if (cmpPriority(cstack.top(), str[i]))//若栈顶元素优先级较高，栈顶元素出栈{if (str[i] == ))//若当前字符是右括号，栈中元素出栈，入字符串数组中，直到遇到({while (!cstack.empty() && cstack.top() != (){temp += cstack.top();cstack.pop();vstr.push_back(temp);temp = "";}cstack.pop();}else//栈中优先级高的元素出栈，入字符串数组，直到优先级低于当前字符{while (!cstack.empty() && cmpPriority(cstack.top(), str[i])){temp += cstack.top();cstack.pop();vstr.push_back(temp);temp = "";}cstack.push(str[i]);}}else//当前字符优先级高于栈顶元素，直接入栈cstack.push(str[i]);}while (!cstack.empty())//栈中还存在运算符时，出栈，存入字符串数组{string temp = "";temp += cstack.top();cstack.pop();vstr.push_back(temp);}return vstr;}

对后缀表达式进行求值，主要是根据运算符取出两

int calcPostExp(vector<string> & vstr)//对后缀表达式进行求值，主要是根据运算符取出两个操作数进行运算{int num, op1, op2;stack<int>opstack;for (int i = 0;i<vstr.size();++i){string temp = vstr[i];if (temp[0] >= 0 && temp[0] <= 9)//如果当前字符串是数字，利用字符串流转化为int型{stringstream ss;ss << temp;ss >> num;opstack.push(num);}else if (vstr[i] == "+")//若是操作符，取出两个操作数，进行运算，并将结果存入{op2 = opstack.top();opstack.pop();op1 = opstack.top();opstack.pop();opstack.push(op1 + op2);}else if (vstr[i] == "-"){op2 = opstack.top();opstack.pop();op1 = opstack.top();opstack.pop();opstack.push(op1 - op2);}else if (vstr[i] == "*"){op2 = opstack.top();opstack.pop();op1 = opstack.top();opstack.pop();opstack.push(op1*op2);}else if (vstr[i] == "/"){op2 = opstack.top();opstack.pop();op1 = opstack.top();opstack.pop();opstack.push(op1 / op2);}}return opstack.top();//最终的栈顶元素就是求解的结果}

到此这篇关于详解Java中缀表达式的实现的文章就介绍到这了,更多相关Java中缀表达式内容请搜索盛行IT以前的文章或继续浏览下面的相关文章希望大家以后多多支持盛行IT！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。

中缀表达式转后缀表达式java,前缀表达式java

目录

相关文章阅读