數據結構實驗之棧二：一般算術表達式轉換成后綴式
Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic PRoblem Description
對于一個基于二元運算符的算術表達式，轉換為對應的后綴式，并輸出之。
Input
輸入一個算術表達式，以‘#’字符作為結束標志。
Output
輸出該表達式轉換所得到的后綴式。
Example Input
a*b+(c-d/e)*f#
Example Output
ab*cde/-f*+
由一般式求后綴式： 1.設立暫時存放運算符的棧； 2.設表達式的結束符為“#”，設運算符的棧底為“#”； 3.若當前字符是操作數，進棧； 4.若當前運算符的優先數高于棧頂運算符，進棧； 5.否則退出棧頂運算符發送給后綴式；//打印出棧頂運算符 6.括號“（”對它之前之后的運算符起隔離作用，“）”可視為自相應左括號開始的表達式的結束符。 代碼來自 http://blog.csdn.net/jinshiyan1995/article/details/43414577
#include <bits/stdc++.h>using namespace std;int ch(char a）//算出優先級{ if(a=='+'||a=='-') return 1; else if(a=='*'||a=='/') return 2; else if(a=='(') return 3; else if(a==')') return 4; return 0;}int main(){ int i,j,top=0; char stacks[1000000],c; while(scanf("%c",&c),c!='#') { if(c>='a'&&c<='z') printf("%c",c); else//分為棧中無元素，當前元素優先級大于棧頂元素，當前元素優先級小于棧頂元素 { if(top==0) { top++; stacks[top]=c; }//從1開始；先計算再賦值，令top指向當前。避免行編輯器那道題中的尷尬。。。 else if(ch(c)>ch(stacks[top])) { if(ch(c)==4)//當前元素為‘）’時，輸出直到‘（’前的棧中元素 { while(stacks[top]!='(') { printf("%c",stacks[top]); top--; } top--;//碰到棧頂為（ ，top--跳過該元素 } else { top++; stacks[top]=c; } } else { if(stacks[top]!='(') { printf("%c",stacks[top]); stacks[top]=c; } else { top++; stacks[top]=c; } } } } while(top) { printf("%c",stacks[top]); top--; } return 0;}新聞熱點
疑難解答
