先說簡單的算術表達式的求值
别慌，真正的算術表達式求值在後面，這隻是前奏
題目來源：HDU http://acm.hdu.edu.cn/showproblem.php?pid=1237
★這題因為沒有括号，是以很簡單，甚至不需要棧和隊列（我就沒用）
相關知識：
算是國小知識了叭，一個規律不知道你們記得否：如果沒有括号，算術表達式一定是一個數一個運算符交替排列的。
思路：
首先輸入一個數，然後接着一定是 一個符号+一個數 的規律直到最後，在過程中，如果有乘除就運算，有減就把數變為相反數，有加就跳到下一個數開始。最後肯定都是加号，把所有數加起來即為答案。
代碼：
#include<stdio.h>
#include<string.h>
int main()
{
double num[200];
int t;
while(~scanf("%d",&t))
{
char c;
int l=0,i;
double sum=t*1.0;
if(t==0&&(c=getchar())=='\n') return 0;
while((c=getchar())!='\n')
{
if(c=='*') {scanf("%d",&t); sum*=t;}
else if (c=='/') {scanf("%d",&t); sum/=t;}
else if (c=='+') {scanf("%d",&t); num[l++]=sum; sum=t*1.0;}
else if (c=='-') {scanf("%d",&t); num[l++]=sum; sum=-t*1.0;}
}
num[l++]=sum;
double ans=0;
for(i=0;i<=l-1;i++) ans+=num[i];
printf("%.2lf\n",ans);
}
}
是不是這題的一股清流233
話不多說，接下來是重頭戲
題目來源：WUSTOJ http://acm.wust.edu.cn/problem.php?id=1642&soj=0
★因為有括号，是以再也沒有那種騷操作 的規律了，老老實實用棧寫（至少我不會其他操作了 ）
相關知識：
首先 括号優先級最高，乘除其次，加減最低，廢話
然後要知道，左括号絕大多數都在運算符右邊（或者第一個字元就是左括号）
最後你要會把字元串裡面的數準确的取出，這也是一個難點
話不多說，看我表演，show time~
思路：
定義兩個棧，sign存放字元，num存放數。先讀字元串，然後從頭開始循環周遊每個字元。如果是+，把1壓入sign；如果是-，把2壓入sign；如果是*,把3壓入sign；如果是/，把4壓入sign；如果是(，把0壓入sign；如果是數字，把它壓入num（并不是簡單的直接壓,我隻是簡略的說 ），然後如果sign不為空，并且下一個字元不為數字（如果是數字，說明目前正在讀取的數沒有讀完，好好了解這裡），這時去sign棧頂，如果是* /，進行sum1運算，是-，進行sum2運算；如果是)，就一直運算到sign棧頂為(,并把(給彈出，還沒完，此時可能需要進行sum1,sum2運算。最後應該還會剩下一些數，但是符号一定隻剩下+了，把他們簡單的處理掉~最後答案就是num棧頂。
上面是較詳細解讀我的代碼，從總體看，我的代碼分為3步。解決（）；解決 / -;解決+*
注意：
别忘了，最後還保留了一個num沒有彈出，把它處理一下。
代碼：
#include<bits/stdc++.h>
using namespace std;
stack<int> sign;
stack<int> num; //雙棧
void sum1(int a) //乘除法
{
int x=num.top(); num.pop();
int y=num.top(); num.pop();
if(a==3) y=y*x;
if(a==4) y=y/x;
num.push(y);
sign.pop();
}
void sum2() //變為相反數
{
int x=num.top(); num.pop();
x=-x;
sign.pop();
num.push(x);
sign.push(1);
}
int main()
{
string s;
while(cin>>s){
int len=s.length();
while(sign.size()) sign.pop(); //清空棧，這是我注意事項裡面的操作
while(num.size()) num.pop();
for(int i=0;i<len;i++){
if(s[i]>='0'&&s[i]<='9'){
if(i&&s[i-1]>='0'&&s[i-1]<='9'){
int a=num.top();
num.pop();
a=a*10+s[i]-'0';
num.push(a);
}
else num.push(s[i]-'0'); //完整取出數
if(sign.size()){
if(i==len-1||((i<len-1)&&(s[i+1]<'0'||s[i+1]>'9'))){
int a=sign.top();
if(a==3||a==4) sum1(a);
else if(a==2) sum2();
}
}
}
else if(s[i]=='+') sign.push(1);
else if(s[i]=='-') sign.push(2);
else if(s[i]=='*') sign.push(3);
else if(s[i]=='/') sign.push(4);
else if(s[i]=='('){
sign.push(0);
if(s[i+1]=='-') num.push(0); //如果括号下一個字元是-,則多補一個0，可能沒有這種情況---》 (-1) 但是萬一有呢？
}
else if(s[i]==')'){
int a=sign.top();
while(a){
int x=num.top(); num.pop();
int y=num.top(); num.pop();
if(a==1) y=y+x;
num.push(y);
sign.pop();
a=sign.top();
}
sign.pop();
if(sign.size()){
a=sign.top();
if(a==3||a==4) sum1(a);
else if(a==2) sum2();
else continue;
}
}
}
while(num.size()>1){
int a=sign.top();
sign.pop();
int x=num.top(); num.pop();
int y=num.top(); num.pop();
if(a==1) y=y+x;
num.push(y);
}
cout<<num.top()<<endl;
}
}
我覺得我的代碼很簡單了，我看别人好多都是100+，我才80多行 。當然，人外有人，大佬看到就見笑了233.