首页 > 代码库 > 四则运算

四则运算

二叉树法

将最终进行的运算符记为根节点,将两边的表达式分别记为左右子树,依次进行直到所有的运算符与数字或字母标在一棵二叉树上。然后对二叉树进行后序遍历即可。

逆波兰式

Reverse Polish notation,RPN,或逆波兰记法),也叫后缀表达式(将运算符写在操作数之后)

一个表达式E的后缀形式可以如下定义:

1)如果E是一个变量或常量,则E的后缀式是E本身。

2)如果E是E1 op E2形式的表达式,这里op是如何二元操作符,则E的后缀式为E1‘E2‘ op,这里E1‘和E2‘分别为E1和E2的后缀式。

3)如果E是(E1)形式的表达式,则E1的后缀式就是E的后缀式。

如:我们平时写a+b,这是中缀表达式,写成后缀表达式就是:ab+

(a+b)*c-(a+b)/e的后缀表达式为:

(a+b)*c-(a+b)/e

→((a+b)*c)((a+b)/e)-

→((a+b)c*)((a+b)e/)-

→(ab+c*)(ab+e/)-

→ab+c*ab+e/-

C语言版

public static void ObjectPoland(String expression)
        {
            Stack<int> nums = new Stack<int>();
            Stack<Oprator> ops = new Stack<Oprator>();
            String[] expNums = expression.Split("+*".ToCharArray(), StringSplitOptions.RemoveEmptyEntries);
            String[] expOps = expression.Split("0123456789".ToCharArray(), StringSplitOptions.RemoveEmptyEntries);
            nums.Push(int.Parse(expNums[0]));
            for (int i = 0; i < expOps.Length; i++)
            {
                Oprator op = ParseToOp(expOps[i]);
                if (ops.Count == 0)
                {
                    ops.Push(op);
                }
                else
                {
                    while (ops.Peek().Prority > op.Prority)
                    {
                        Oprator top = ops.Pop();
                        int result = top.Compute(nums.Pop(), nums.Pop());
                        nums.Push(result);
                    }
                    ops.Push(op);
                }
                nums.Push(int.Parse(expNums[i + 1]));
            }
            while (ops.Count != 0)
            {
                Oprator top = ops.Pop();
                int result = top.Compute(nums.Pop(), nums.Pop());
                nums.Push(result);
            }
            Console.WriteLine("{0}={1}", expression, nums.Pop());
        }
        public static Oprator ParseToOp(String op)
        {
            switch (op)
            {
                case "+": return new Oprator(OpType.Add, 1);
                case "-": return new Oprator(OpType.Minus, 2);
                case "*": return new Oprator(OpType.Muli, 4);
                case "/": return new Oprator(OpType.Div, 5);
                default: return null;
            }
        }
        enum OpType
        {
            Add, Minus, Muli, Div
        }
        class Oprator
        {
            OpType opType;
            int prority;

            public Oprator(OpType opType, int prority)
            {
                this.opType = opType;
                this.prority = prority;
            }

            public OpType OpType
            {
                get
                {
                    return opType;
                }
            }

            public int Prority
            {
                get
                {
                    return prority;
                }
            }

            public int Compute(int n1, int n2)
            {
                switch (OpType)
                {
                    case OpType.Add: return n1 + n2;
                    case OpType.Minus: return n1 - n2;
                    case OpType.Muli: return n1 * n2;
                    case OpType.Div:
                        if (n2 == 0)
                        {
                            return 0;
                        }
                        return n1 / n2;
                    default: return 0;
                }
            }
        }

C# 实际运用版

public static void Compute()                                //加减乘除四则运算
        {
            Console.WriteLine("请输入您要算的式子:");
            String expression = Console.ReadLine();
            //Console.WriteLine(expression);
            // 拆分字符串得到 运算数 及运算符
            String[] nums = expression.Split("+-*/".ToCharArray(),StringSplitOptions.RemoveEmptyEntries);
            String[] ops = expression.Split("0123456789".ToCharArray(),StringSplitOptions.RemoveEmptyEntries);

            // 运算
            for (int i = 0; i < ops.Length; i++)
            {
                // 先乘除
                if (/*ops[i] != null &&*/ (ops[i] == "*" || ops[i] == "/"))
                {
                    // 找两数
                    int num1 = int.Parse(nums[i]);
                    int num2 = int.Parse(nums[i + 1]);

                    // 计算结果
                    int result = ComputeByOp(num1, num2, ops[i]);
                    nums[i] = result.ToString();

                    // 运算数和运算符数组向前移动
                    Move(nums, i + 1);
                    Move(ops, i);

                    i--;
                }
            }
            for (int i = 0; i < ops.Length; i++)
            {
                // 后加减
                if (/*ops[i] != null &&*/ (ops[i] == "+" || ops[i] == "-"))
                {
                    // 找两数
                    int num1 = int.Parse(nums[i]);
                    int num2 = int.Parse(nums[i + 1]);

                    // 计算结果
                    int result = ComputeByOp(num1, num2, ops[i]);
                    nums[i] = result.ToString();

                    // 运算数和运算符数组向前移动
                    Move(nums, i + 1);
                    Move(ops, i);
                    i--;
                }
            }

            Console.WriteLine(nums[0]);
        }
        public static void Move(string[] arr, int start)
        {
            arr[start] = null;
            for (int i = start; i < arr.Length - 1; i++)
            {
                if (arr[i + 1] != null)
                {
                    string temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                }
            }
        }
        public static int ComputeByOp(int num1, int num2, String op)
        {
            switch (op)
            {
                case "+": return num1 + num2;
                case "-": return num1 - num2;
                case "*": return num1 * num2;
                case "/": return num1 / num2;
                default:
                    return 0;
            }
        }    

C/C++语言版

//#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<stack>
#include<math.h>
#include<string.h>
#define max 100
using namespace std;
charex[max];/*存储后缀表达式*/
 
void trans()
{/*将算术表达式转化为后缀表达式*/
charstr[max];/*存储原算术表达式*/
charstack[max];/*作为栈使用*/
charch;
intsum,i,j,t,top=0;
printf("*****************************************\n");
printf("*输入一个求值的表达式,以#结束。*\n");
printf("******************************************\n");
printf("算数表达式:");
i=0;/*获取用户输入的表达式*/
do{
i++;
//cin>>str[i];/*此步我用的是C++C语言的话在后面之所以用这个有一点区别都*/
scanf("%c",&str[i]);
}while(str[i]!=‘#‘&&i!=max);
sum=i;
t=1;i=1;
ch=str[i];i++;
//
while(ch!=‘#‘)
{
switch(ch)
{
case‘(‘:/*判定为左括号*/
top++;stack[top]=ch;
break;
case‘)‘:/*判定为右括号*/
while(stack[top]!=‘(‘)
{
ex[t]=stack[top];top--;t++;
}
top--;
break;
case‘+‘:/*判定为加减号*/
case‘-‘:
while(top!=0&&stack[top]!=‘(‘)
{
ex[t]=stack[top];
top--;
t++;
}
top++;
stack[top]=ch;
break;
case‘*‘:/*判定为乘除号*/
case‘/‘:
while(stack[top]==‘*‘||stack[top]==‘/‘)
{
ex[t]=stack[top];
top--;
t++;
}
top++;
stack[top]=ch;
break;
case‘‘:break;
default:
while(ch>=‘0‘&&ch<=‘9‘)
{/*判定为数字*/
ex[t]=ch;t++;
ch=str[i];i++;
}
i--;
ex[t]=‘‘;t++;
}
ch=str[i];i++;
}
while(top!=0)
{
ex[t]=stack[top];
t++;top--;
}
ex[t]=‘‘;
printf("\n\t原来表达式:");
for(j=1;j<sum;j++)
printf("%c",str[j]);
printf("\n\t逆波兰式:",ex);
for(j=1;j<t;j++)
printf("%c",ex[j]);
}
 
void compvalue()
{/*计算后缀表达式的值*/
floatstack[max],d;/*作为栈使用*/
charch;
intt=1,top=0;/*t为ex下标,top为stack下标*/
ch=ex[t];t++;
while(ch!=‘‘)
{
switch(ch)
{
case‘+‘:
stack[top-1]=stack[top-1]+stack[top];
top--;
break;
case‘-‘:
stack[top-1]=stack[top-1]-stack[top];
top--;
break;
case‘*‘:
stack[top-1]=stack[top-1]*stack[top];
top--;
break;
case‘/‘:
if(stack[top]!=0)stack[top-1]=stack[top-1]/stack[top];
else
{
printf("\n\t除零错误!\n");
exit(0);/*异常退出*/
}
top--;
break;
default:
d=0;
while(ch>=‘0‘&&ch<=‘9‘)
{
d=10*d+ch-‘0‘;/*将数字字符转化为对应的数值*/
ch=ex[t];t++;
}
top++;
stack[top]=d;
}
ch=ex[t];
t++;
}
printf("\n\t计算结果:%g\n",stack[top]);
}
 
int main()
{
trans();
compvalue();
system("pause");
return0;
}

数据结构版

int precede(char op)
{ int x;
switch(op)
{
case ‘*‘: x=2; break;
case ‘/‘: x=2; break;
case ‘+‘: x=1; break;
case ‘-‘: x=1; break;
default : x=0;
}
return x;
}
char *RPExpression(char *e)
{/* 返回e的逆波兰式 */
char *c;
c=(char*)malloc(sizeof(char)*20); //不能用char c[]
Stack s1;
InitStack(s1);
int i=0,j=0;
char ch;
Push(s1,‘@‘);
ch=e[i++];
while(ch!= 0)
{
if(ch==‘(‘)
{
Push(s1,ch);
ch=e[i++];
}
else if(ch==‘)‘)
{
while(Top(s1)!=‘(‘)
{
Pop(s1,c[j++]);
}
/* to[j++]=pop(&s1);*/
Pop(s1,ch);
ch=e[i++];
}
else if(ch==‘+‘||ch==‘-‘||ch==‘*‘||ch==‘/‘)
{
char w;
w=Top(s1);
while(precede(w)>=precede(ch))
{
Pop(s1,c[j++]);
w=Top(s1);
}
Push(s1,ch);
ch=e[i++];
}
else
{
//while((ch<=‘z‘&&ch>=‘a‘)||(ch<=‘Z‘ && ch>=‘A‘)){
c[j++]=ch;
ch=e[i++];
//}
//c[j++]=‘ ‘;
}
}
Pop(s1,ch);
while(ch!=‘@‘)
{
c[j++]=ch;
Pop(s1,ch);
}
//c[j++]=;
c[j++]=0;
return c;
}

Pascal

由键盘输入一个算术表达式,求出它的逆波兰式,并输出数值。
    例:((3+4)*3+15)/3  的逆波兰式为3 4 + 3 * 15 + 3 /
         计算结果为12
const m=100;
type stack=array[1..m] of integer;
var s:stack;
    a:string;
    t,i,j,k,len:integer;
procedure push(x:integer);{进栈}
  begin
    t:=t+1;
    s[t]:=x;
  end;
function pop:integer;{出栈}
  begin
    pop:=s[t];
    t:=t-1;
  end;
begin
  readln(a); {读入后缀表达式}
  len:=length(a);  
  i:=1;      {后缀表达式字符指针初始化}
  t:=0;      {栈初始化}
  while i<=len do  {处理后缀表达式,直至结束}
    begin
      case a[i] of
‘0‘..‘9‘:begin
                   k:=0;
                   while a[i]<>’.’ do 
                     begin      {从s中取出一个完整的操作数k}
                       k:=10*k+ord(a[i])-48;
                       i:=i+1;
                     end;
                   push(k);{把k压栈}
                 end;
 ‘+‘:push(pop+pop);
     {从栈s中取出栈顶的两个数进行加法运算,然后将结果在压栈}
‘-‘:begin  {从栈s中取出栈顶的两个数进行减法运算,然后将结果在压栈}
              j:=pop;
              push(pop-j);
     end;
 ‘*‘:push(pop*pop); 
    {从栈s中取出栈顶的两个数进行乘法运算,然后将结果在压栈}
  ‘/‘:begin  {从栈s中取出栈顶的两个数进行除法运算,然后将结果在压栈}
              j:=pop;
              push(pop div j);
      end;
end;{case}
i:=i+1;
  end;{while}
  writeln(pop);  {取出栈顶元素,即时表达式的最后结果}
end;

  

 

四则运算